AC日记——城市 洛谷 P1401

题目描述

N(2<=n<=200)个城市，M(1<=m<=40000)条无向边，你要找T(1<=T<=200)条从城市1到城市N的路，使得最长的边的长度最小，边不能重复用。

输入输出格式

输入格式：

第1行三个整数N,M,T用空格隔开。

第2行到P+1行，每行包括三个整数Ai,Bi,Li表示城市Ai到城市Bi之间有一条长度为Li的道路。

输出格式：

输出只有一行，包含一个整数，即经过的这些道路中最长的路的最小长度。

输入输出样例

输入样例#1：

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

输出样例#1：

5

思路：

　　网络流；

　　二分答案；

　　然后删边；

　　然后看最大流是否大于T；

来，上代码：

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

#define maxn 205
#define INF 0x7fffffff

using namespace std;

struct EdgeType {
    int v,l,e,f;
};
struct EdgeType edge[maxn*maxn*4];

int s,t,deep[maxn];
int n,m,T,cnt=1,head[maxn],maxl,minl=0x7fffffff;

char Cget;

inline void in(int &now)
{
    now=0,Cget=getchar();
    while(Cget>'9'||Cget<'0') Cget=getchar();
    while(Cget>='0'&&Cget<='9')
    {
        now=now*10+Cget-'0';
        Cget=getchar();
    }
}

bool bfs()
{
    queue<int>que;
    for(int i=s;i<=t;i++) deep[i]=-1;
    deep[s]=0,que.push(s);
    while(!que.empty())
    {
        int now=que.front();que.pop();
        for(int i=head[now];i;i=edge[i].e)
        {
            if(deep[edge[i].v]<0&&edge[i].f>0)
            {
                deep[edge[i].v]=deep[now]+1;
                if(edge[i].v==t) return true;
                que.push(edge[i].v);
            }
        }
    }
    return false;
}

int flowing(int now,int flow)
{
    if(now==t||flow<=0) return flow;
    int oldflow=0;
    for(int i=head[now];i;i=edge[i].e)
    {
        if(deep[edge[i].v]!=deep[now]+1||edge[i].f<=0) continue;
        int pos=flowing(edge[i].v,min(flow,edge[i].f));
        if(pos>0)
        {
            flow-=pos;
            oldflow+=pos;
            edge[i].f-=pos;
            edge[i^1].f+=pos;
            if(flow==0) return oldflow;
        }
    }
    if(oldflow==0) deep[now]=-1;
    return oldflow;
}

bool check(int pos)
{
    for(int i=2;i<=cnt;i+=2)
    {
        edge[i^1].f=0;
        if(edge[i].l<=pos) edge[i].f=1;
        else edge[i].f=0;
    }
    int ans=0;
    while(bfs())
    ans+=flowing(s,INF);
    if(ans>=T) return true;
    else return false;
}

int main()
{
    in(n),in(m),in(T);
    int u,v,li;s=1,t=n;
    while(m--)
    {
        in(u),in(v),in(li);if(li>maxl) maxl=li;if(li<minl) minl=li;
        edge[++cnt].v=v,edge[cnt].l=li,edge[cnt].e=head[u],head[u]=cnt;
        edge[++cnt].v=u,edge[cnt].l=li,edge[cnt].e=head[v],head[v]=cnt;
        edge[++cnt].v=u,edge[cnt].l=li,edge[cnt].e=head[v],head[v]=cnt;
        edge[++cnt].v=v,edge[cnt].l=li,edge[cnt].e=head[u],head[u]=cnt;
    }
    int l=minl,r=maxl,ans,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(check(mid)) ans=mid,r=mid-1;
        else l=mid+1;
    }
    cout<<ans;
    return 0;
}