poj 2455 二分+最大流-蒲公英云

poj 2455 二分+最大流

这个因为点少用邻接矩阵做的。

题意：求由1到n的t条不重复路径中最大边权值的最小值。

思路：先对边权进行排序，然后二分边权值，建图求从1到n的最大流，当最大流为t时便求出答案。

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 210
int n,m,t;
int a,b,c;
int map[210][210];
struct Edge
{
    int u,v,w;
}edge[40001];
bool cmp(Edge a,Edge b)
{
    return a.w<b.w;
}
int sap()
{
    int pre[N],dis[N],gap[N],aug=-1,maxflow=0,u;
    int s=1,t=n;
    memset(gap,0,sizeof(gap));
    memset(dis,0,sizeof(dis));
    u=pre[s]=s;
    gap[0]=t;
    while(dis[s]<t)
    {
loop:for(int i=1;i<=t;i++)
     {
         if(map[u][i]&&dis[u]==dis[i]+1)
         {
             if(aug==-1||aug>map[u][i])
                 aug=map[u][i];
             pre[i]=u;
             u=i;
             if(u==t)
             {
                 maxflow+=aug;
                 for(int v=t;v!=s;v=pre[v])
                 {
                     map[pre[v]][v]-=aug;
                     map[v][pre[v]]+=aug;
                 }
                 aug=-1;
                 u=s;
             }
             goto loop;
         }
     }
     int mindis=t-1;
     for(int i=1;i<=t;i++)
         if(map[u][i]&&dis[i]<mindis)
             mindis=dis[i];
     if((--gap[dis[u]])==0) break;
     gap[dis[u]=mindis+1]++;
     u=pre[u];
    }
    return maxflow;
}
void build(int x)
{
    memset(map,0,sizeof(map));
    for(int i=0;i<=x;i++)
    {
        int u,v;
        u=edge[i].u;
        v=edge[i].v;
        map[u][v]++;
        map[v][u]++;
    }
}
bool check(int x)
{
    build(x);
    int maxflow=sap();
    if(maxflow>=t)
    {
        return true;
    }
    return false;
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&t)!=EOF)
    {
        memset(edge,0,sizeof(edge));
        memset(map,0,sizeof(map));
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            edge[i].u=a;
            edge[i].v=b;
            edge[i].w=c;
        }
        sort(edge,edge+m,cmp);
        int l=0,r=m-1;
        while(r>=l)
        {
            int mid=(l+r)>>1;
            if(check(mid))
            {
                r=mid-1;
            }
            else l=mid+1;
        }
        printf("%d\n",edge[r+1].w);
    }
}