【BZOJ 3345】[Pku2914] Minimum Cut

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3345

这题就是一个全局最小割,其中分治最小割的做法肯定是正确的
于是水之,1.4s卡过

全局最小割专门的算法还是很优越的样子
无论是时间复杂度或是编程复杂度
但我这个蒟蒻学不会QAQ
弃坑

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;
  
const int N = 850+9;
const int M = 8500*2+9;
const int INF = 100000000;
  
int head[N],nxt[M],to[M],flow[M],cur[N];
int n,m,vout=INF,cnt,id[N],dis[N],pur,T=1;
queue<int> que;
  
inline void Add_Edge(int u, int v, int w) {
    to[++T] = v; nxt[T] = head[u]; head[u] = T; flow[T] = w;
    to[++T] = u; nxt[T] = head[v]; head[v] = T; flow[T] = w;
}
  
inline int read(){
    char c=getchar(); int ret=0,f=1;
    while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
    while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar();
    return ret*f;
}
  
inline bool BFS(int s, int t) {
    memset(dis,-1,sizeof(dis));
    que.push(s); dis[s] = 0;
      
    while (!que.empty()) {
        int w = que.front(); que.pop();
        for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) 
            dis[to[i]] = dis[w] + 1, que.push(to[i]);
    }
    return ~dis[t];
}
  
int DFS(int w, int f) {
    if (w == pur) return f;
    else {
        int ret = 0;
        for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) {
            int tmp = DFS(to[i], min(f, flow[i]));
            flow[i] -= tmp; flow[i^1] += tmp;
            ret += tmp; f -= tmp; if (!f) return ret;
        }
        return ret;
    }   
}
  
inline int Dinic(int s, int t){
    int ret = 0; pur = t;
    while (BFS(s,t)) {
        memcpy(cur,head,sizeof(head));
        ret += DFS(s,INF);
    } return ret;
}
  
void SIGN(int w) {
    dis[w] = 1;
    for (int i=head[w];i;i=nxt[i]) 
        if (!~dis[to[i]] && flow[i]) SIGN(to[i]);
}
  
void solve(int l , int r){
    if (l >= r) return ;
    static int tmp[N]; int L=l-1, R=r+1;
      
    for (int i=2;i<=T;i+=2) flow[i] = flow[i^1] = flow[i] + flow[i^1] >> 1;
    vout = min(vout, Dinic(id[l],id[r]));
      
    memset(dis,-1,sizeof(dis)); SIGN(id[l]); 
    for (int i=l;i<=r;i++) 
        if (~dis[id[i]]) tmp[++L] = id[i];
        else tmp[--R] = id[i];
    for (int i=l;i<=r;i++) id[i] = tmp[i];
    solve(l,L); solve(R,r);
}
  
int main(){
    n = read(); m = read();
    for (int i=1,u,v,w;i<=m;i++) u = read(), v = read(), w = read(), Add_Edge(u,v,w);
    for (int i=1;i<=n;i++) id[i] = i; solve(1,n); 
    printf("%d\n",vout);
    return 0;
}