一直不明白为什么我的耗时几百毫秒，明明差不多的程序啊，我改来改去还是几百毫秒。
...一个小时后：明白了，原来把最大值0x3f（77）取0x3f3f3f3f就把时间缩短为16ms了。可是为什么原来那样没有WA呢？哦，明白了，因为最大值写小了，dicnic会多跑几遍。
嗯顺便：0x3f3f3f3f也就是1061109567，也就是10^9级别的，是一个很大的数，而且加上一个10^9级别以下的数字也不会溢出。所以很多时候最大值取这个会比较好。最大的int是0x7fffffff，可以用常量INT_MAX 代替。
#include<cstdio> #include<algorithm> #include<queue> #include<cstring> using namespace std; int arc[201][201], d[201], q[201]; int m, n, ans,tans; bool bfs() { memset(d, -1, sizeof d); queue<int>q; q.push(1); d[1] = 0; while(!q.empty()) { int i,k=q.front(); q.pop(); for(i = 1; i <= n; i++) if(arc[k][i] > 0 && d[i] == -1) { d[i] = d[k] + 1; q.push(i); } } return d[n]>0; } int dinic (int k, int low) { if(k == n)return low; int a,i; for(i = 1; i <= n; i++) if(d[i] == d[k] + 1&& arc[k][i] > 0 &&(a = dinic(i, min(low, arc[k][i])))) { arc[k][i] -= a; arc[i][k] += a; return a; } return 0; } int main() { while(~scanf("%d%d", &m, &n)) { memset(arc, 0, sizeof arc); for(int i = 0; i < m; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); arc[u][v] += c; } ans = 0; while(bfs()) while(tans=dinic(1, 0X3f3f3f3f)) ans += tans; printf("%d ",ans); } return 0; }