POJ 2455 二分最大流。

Description

Input

Output

Sample Input

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3

Sample Output

5

Hint

Source

题意： 找k条不相交的路径，使得最大边的权值最小，

解题思路：二分权值，然后建图，跑最大流，记着是双向边，单向边wa了好多次。

代码：

/* ***********************************************
Author :xianxingwuguan
Created Time :2014-1-25 14:49:49
File Name :3.cpp
************************************************ */

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
typedef int ll;
const ll inf=10000000;
const ll maxn=2000;
ll head[maxn],tol,dep[maxn];
struct node 
{
      ll from,to,next,cap;
      node(){};
      node(ll from,ll to, ll next,ll cap):from(from),to(to),next(next),cap(cap){}
}edge[1000000],ss[1000000];
void add(ll u,ll v,ll cap)
{
      edge[tol]=node(u,v,head[u],cap);
      head[u]=tol++;
      edge[tol]=node(v,u,head[v],0);
      head[v]=tol++;
}
bool bfs(ll s,ll t)
{
       ll que[maxn],front=0,rear=0;
       memset(dep,-1,sizeof(dep));
       dep[s]=0;que[rear++]=s;
       while(front!=rear)
       {
              ll u=que[front++];front%=maxn;
              for(ll i=head[u];i!=-1;i=edge[i].next)
              {
                     ll v=edge[i].to;
                     if(edge[i].cap>0&&dep[v]==-1)
                     {
                            dep[v]=dep[u]+1;
                            que[rear++]=v;
                            rear%=maxn;
                            if(v==t)return 1;
                     }
              }
       }
       return 0;
}

ll dinic(ll s,ll t)
{
      ll res=0;
      while(bfs(s,t))
      {
	     ll Stack[maxn],top,cur[maxn];
	     memcpy(cur,head,sizeof(head));
	     top=0;
	     ll u=s;
	     while(1)
	     {
		    if(t==u)
		    {
			   ll min=inf;
			   ll loc;
			   for(ll i=0;i<top;i++)
		          if(min>edge[Stack[i]].cap)
			   {
				  min=edge[Stack[i]].cap;
				  loc=i;
			   }
			   for(ll i=0;i<top;i++)
			   {
				  edge[Stack[i]].cap-=min;
				  edge[Stack[i]^1].cap+=min;
			   }
			   res+=min;
			   top=loc;
                        u=edge[Stack[top]].from;
		    }
		    for(ll i=cur[u];i!=-1;cur[u]=i=edge[i].next)
			   if(dep[edge[i].to]==dep[u]+1&&edge[i].cap>0)break;
		    if(cur[u]!=-1)
		    {
			   Stack[top++]=cur[u];
			   u=edge[cur[u]].to;
		    }
		    else 
		    {
			   if(top==0)break;
			   dep[u]=-1;
			   u=edge[Stack[--top]].from;
		    }
	     }
      }
      return res;
}

int main()
{
     int n,m,t,i,j,k;
     while(cin>>n>>m>>t)
     {
           int left=inf,right=-inf;
	    for(i=1;i<=m;i++)
	    {
		   scanf("%d%d%d",&ss[i].from,&ss[i].to,&ss[i].cap);
		   if(left>ss[i].cap)left=ss[i].cap;
		   if(right<ss[i].cap)right=ss[i].cap;
	    }
	    right=1000000;
	    int ans;
	    while(left<=right)
	    {
		   memset(head,-1,sizeof(head));tol=0;
		   int mid=(left+right)>>1;
		   for(i=1;i<=m;i++)
			  if(ss[i].cap<=mid)
				 add(ss[i].from,ss[i].to,1),add(ss[i].to,ss[i].from,1);
		   if(dinic(1,n)>=t)right=mid-1,ans=mid;
		   else left=mid+1;
	    }
	    cout<<ans<<endl;
     }
     return 0;
}

POJ 2455 二分最大流。

原文：http://blog.csdn.net/xianxingwuguan1/article/details/18778113