题意：
给定n个点m条边的无向图 K值
下面给定m条边及其边权
问：
起点为1，终点为n
找到至少K条边不相交的路径，输出这个方案中所有边的最大边权
思路：
二分答案+网络流，使得汇点>=K即为可行解
#include #include #include #include #include #include #include #include #include #include #include #include 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 edge[Stack[i]].cap) { min=edge[Stack[i]].cap; loc=i; } for(ll i=0;i 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 = 0 ; for(i=1;i<=m;i++) { scanf("%d%d%d",&ss[i].from,&ss[i].to,&ss[i].cap); right = max(right, ss[i].cap); left = min(left, ss[i].cap); } int ans = inf; while(left<=right) { int mid=(left+right)>>1; memset(head,-1,sizeof(head));tol=0; 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 = min(ans, mid); else left=mid+1; } cout<