[洛谷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：

Solution

二分答案+网络流....
本来想用k长路做,然后发现每条边只能经过1次

那么,不就是网络流吗,容量为1,表示做多可以跑一次

那么具体实现,二分一个边权,只有当小于等于这个边权的才能跑,容量为1,反向边容量为0

因为是无向边,所以每次本来应该是4条边的,但跑的是最大流,所以容量为0的两条边就可以省略了,二分判断合法的方式就是看当前最大流能不能跑满T,T为题目输入

Code

#include<bits/stdc++.h>
#define lol long long
#define Min(a,b) (a)<(b)?(a):(b)
#define Max(a,b) (a)>(b)?(a):(b)
 
using namespace std;

const int N=210,M=4e4+10;
const int inf=2e9;

void in(int &ans)
{
    ans=0;int f=1; char i=getchar();
    while(i<'0'||i>'9'){if(i=='-') f=-1; i=getchar();}
    while(i>='0'&&i<='9') ans=(ans<<3)+(ans<<1)+i-'0',i=getchar();
    ans*=f;
}

int n,m,T,cur=-1;
int l=inf,r=-inf;
int a[M],b[M],c[M];
int to[M<<1],head[N],nex[M<<1],vis[M<<1],cap[M<<1];
int lev[N];

inline void add(int a,int b,int c)
{
    to[++cur]=b,nex[cur]=head[a];
    cap[cur]=c,head[a]=cur;
}

bool bfs(int s,int t)
{
    queue<int>q;
    memset(lev,-1,sizeof(lev));
    q.push(s); lev[s]=0;
    while(!q.empty()) {
		int u=q.front(); q.pop();
		for(int i=head[u];i;i=nex[i]) {
		    if(lev[to[i]]==-1 && cap[i]) {
				lev[to[i]]=lev[u]+1; q.push(to[i]);
		   }
		}
    }
    return lev[t]!=-1;
}

int dfs(int s,int f,int t,int rest=0)
{
    if(s==t) return f;
    for(int i=head[s];i;i=nex[i]) {
		if(lev[to[i]]==lev[s]+1 && cap[i]) {
		    int r=dfs(to[i],Min(cap[i],f-rest),t);
		    if(r>0) {
				rest+=r;
				cap[i]-=r,cap[i^1]+=r;
		    }
		}
    }
    if(!rest) lev[s]=-1;
    return rest;
}

bool check(int mid,int ans=0)
{
    memset(head,0,sizeof(head)); cur=-1;
    for(int i=1;i<=m;i++) {
		if(c[i]<=mid) add(a[i],b[i],1),add(b[i],a[i],1);
    }
    while(bfs(1,n))
		while(int c=dfs(1,inf,n)) ans+=c;
    return ans>=T;
}

int main()
{
    in(n),in(m),in(T);
    for(int i=1;i<=m;i++) {
		in(a[i]),in(b[i]),in(c[i]);
		l=Min(l,c[i]),r=Max(r,c[i]);
    }
    while(l<r) {
		int mid=l+r>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
    }
    printf("%d
",r);
}