//	Accepted	808K	391MS	C++	2314B	2012-09-12 09:27:43
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define inf 10000000
struct node 
{
	int u,v,w;
}edge[40010];
int n,p,t,vist[210],opt[210],cf[210][210],dui[210];
void creat(int l)
{
	int i;
	 memset(cf,0,sizeof(cf));
     for(i=1;i<=l;i++)
	 {
		 cf[edge[i].u][edge[i].v]++;
		 cf[edge[i].v][edge[i].u]=cf[edge[i].u][edge[i].v];
	 }
	 return;
}
int bfs() 
{ 
    memset(vist,0,sizeof(vist)); 
    memset(opt,0,sizeof(opt)); 
    int rear=0,front=0,x,i; 
    opt[1]=0; 
    vist[1]=1; 
    dui[rear]=1; 
    front++; 
    while(rear!=front) 
    { 
        x=dui[rear]; 
        rear++; 
        for(i=1;i<=n;i++) 
        { 
            if(vist[i]==0&&cf[x][i]>0) 
            { 
                vist[i]=1; 
                dui[front]=i; 
                front++; 
                opt[i]=opt[x]+1; 
            } 
        } 
    } 
    if(vist[n]==1) 
    { 
        return 1; 
    } 
    else
    { 
        return 0; 
    } 
} 
int flow; 
int min(int a,int b)
{
	if(a<b)  return a;
	else   return b;
}
int dfs(int x,int cp) 
{ 
    int i,tem,cmp; 
    tem=cp;
    if(x==n) 
    { 
        
        flow+=cp; 
        return cp; 
    } 
        for(i=1;i<=n;i++) 
        { 
            if(opt[x]==opt[i]-1&&cf[x][i]>0) 
            { 
                cmp=dfs(i,min(cf[x][i],tem)); 
				cf[x][i]-=cmp;
				cf[i][x]+=cmp;
				tem-=cmp;
            } 
        } 
    return cp-tem; 
} 
int dinic()
{
	int zf=0;
	while(bfs())
	{
		flow=0;
		dfs(1,inf);
        zf+=flow;
	}
	return zf;
}
int cmp(const void *a,const void *b)
{
	struct node *x=(node *)a;
	struct node *y=(node *)b;
	return (x->w)-(y->w);
}
int main()
{
	int i,j,right,left,mid,high,liu;
	scanf("%d%d%d",&n,&p,&t);
	for(i=1;i<=p;i++)
	{
		scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);
	}
    qsort(edge+1,p,sizeof(struct node),cmp);
    /*for(i=1;i<=p;i++)
	{
	    printf("%d %d %d\n",edge[i].u,edge[i].v,edge[i].w);
	}*/  //correct
	left=1;
	right=p;
	high=inf;
	while(left<=right)
	{
		mid=(left+right)/2;
		creat(mid);
		liu=dinic();
		if(liu>=t)
		{
			if(edge[mid].w<high)
			{
				high=edge[mid].w;
			}
			right=mid-1;
		}
		else
		{
           left=mid+1;
		}
	}
	printf("%d\n",high);
	return 0;
}

• Re:ac的意想不到，挺高兴的，只可惜思路不是自己的，附代码 (2672) liach 2016-10-25 14:27:08