题目传送门: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; }