1.最短路径转最大流
trick:无向图的话,就是建立反边,并且容量均为设定的f[i]即可
思路就是:二分答案x,然后对于权值大于x的容量都设为0,小于等于x的话f[i]设为1,源点是1,汇点是n,如果最大流的值>=K,那么x可以作为答案
代码:
#include<bits/stdc++.h>#define x first
#define y second
#define endl '\n'
#define int long longusing namespace std;const int N=2e5,M=2e5,INF=1e15;//根据边的大小,来调整N,M,INFint n,m,S,T,K;
int h[N],e[M],f[M],ne[M],idx,w[M];//l数组记录的是每条边的下界
int q[N],d[N],cur[N];//A[i]表示所有进入i这个点的边的流量下界之和-所有从i点出去的边的流量下界之和void add(int a,int b,int c){e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;e[idx]=a,w[idx]=c,ne[idx]=h[b],h[b]=idx++;
}bool bfs(){//规划分层图,然后判断是否存在增广路int hh=0,tt=0;memset(d,-1,sizeof d);q[0]=S,d[S]=0,cur[S]=h[S];//起点的层数为0while(hh<=tt){int t=q[hh++];for(int i=h[t];~i;i=ne[i]){int ver=e[i];if(d[ver]==-1&&f[i]){//只有这条边有流量的时候,才能继续走下去d[ver]=d[t]+1;cur[ver]=h[ver];if(ver==T)return true;//如果能搜到T的话,那么就说明可以找到一条增广路q[++tt]=ver;}}}return false;
}int find(int u,int limit){if(u==T) return limit;int flow=0;for(int i=cur[u];~i&&flow<limit;i=ne[i]){//当前弧优化cur[u]=i;int ver=e[i];if(d[ver]==d[u]+1&&f[i]){int t=find(ver,min(f[i],limit-flow));if(!t) d[ver]= -1;f[i]-=t,f[i^1]+=t,flow+=t;}}return flow;
}int dinic(){int ans=0,flow;while(bfs()) while(flow=find(S,INF)) ans+=flow;return ans;
}bool check(int x){for(int i=0;i<idx;i++){if(w[i]<=x) f[i]=1;else f[i]=0;}if(dinic()>=K) return true;return false;
}void slove(){cin>>n>>m>>K;memset(h,-1,sizeof h);for(int i=1;i<=m;i++){int a,b,c;cin>>a>>b>>c;add(a,b,c);} S=1,T=n;int l=1,r=1e6;while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}cout<<l<<endl;
}signed main(){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int T=1;while(T--) slove();
}