这个题的增广路完全可以不用spfa，因为边的权值只有0和1
改之前TLE，改完之后438MS，TLE的都来试试吧
另外这题双向边 重边按照两条处理 别被坑了
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define c(a) memset(a,0,sizeof a);
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
#define M 210
struct abcd{int from,to,f;}edges[40100];
int m,n,T,s,t,ans,top;
int table[M][M];
void initialize(){c(table);ans=0;}
int f[M],from[M],q[65540];
unsigned short r,h;
bool maxflow()
{
	int i;c(f);
	f[s]=1;q[++h]=s;
	while(r!=h)
	{
		r++;
		for(i=1;i<=n;i++)if(!f[i])if(table[q[r]][i])f[i]=1,from[i]=q[r],q[++h]=i;
	}
	if(!f[t])return false;
	ans++;
	for(i=n;i^1;i=from[i])table[from[i]][i]--,table[i][from[i]]++;
	return true;
}
bool Judge(int x)
{
	initialize();
	for(int i=1;i<=m;i++)if(edges[i].f<=x)table[edges[i].from][edges[i].to]++,table[edges[i].to][edges[i].from]++;
	while(maxflow());
	if(ans>=T)return 1;
	return 0;
}
int divide(int x,int y)
{
	int mid=x+y>>1;
	if(x+1>=y){if(Judge(x))return x;return y;}
	if(Judge(mid))return divide(x,mid);
	else return divide(mid,y);
}
int main()
{
	int i,x,y,z;
	scanf("%d%d%d",&n,&m,&T);s=1;t=n;
	for(i=1;i<=m;i++)scanf("%d%d%d",&edges[i].from,&edges[i].to,&edges[i].f),top=max(top,edges[i].f);
	printf("%d",divide(1,top));

}

• Re:最大流套模板的TLE的注意 (7) 429073576 2016-03-13 10:50:38