一直不明白为什么我的耗时几百毫秒，明明差不多的程序啊，我改来改去还是几百毫秒。 ...一个小时后：明白了，原来把最大值0x3f（77）取0x3f3f3f3f就把时间缩短为16ms了。可是为什么原来那样没有WA呢？哦，明白了，因为最大值写小了，dicnic会多跑几遍。 嗯顺便：0x3f3f3f3f也就是1061109567，也就是10^9级别的，是一个很大的数，而且加上一个10^9级别以下的数字也不会溢出。所以很多时候最大值取这个会比较好。最大的int是0x7fffffff，可以用常量INT_MAX 代替。
代码语言：javascript复制#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("%dn",ans);
}
return 0;
}
