poj 2455 Secret Milking Machine 二分+最大流
题意:
给一图,求从点1到n的t条边不相交的路径,目标是最小化最t条路径中的最大边,输出该最大边。
分析:
求最值的问题满足单调性都可以用二分来做,二分是加速的枚举方法。这题二分枚举最大边建图,每次用长度小于等于二分值的边建图并置容量为1,求最大流即可。
代码:
//poj 2455 //sep9 #include <iostream> #include <queue> #include <algorithm> using namespace std; const int maxN=256; const int maxM=40012; struct Edge { int v,f,nxt; }e[maxM*2+10]; queue<int> que; int src,sink; int g[maxN+10]; int nume; bool vis[maxN+10]; int dist[maxN+10]; int n,p,t; int a[maxM],b[maxM],c[maxM]; void addedge(int u,int v,int c) { e[++nume].v=v;e[nume].f=c;e[nume].nxt=g[u];g[u]=nume; e[++nume].v=u;e[nume].f=c;e[nume].nxt=g[v];g[v]=nume; } void init() { memset(g,0,sizeof(g)); nume=1; } int bfs() { while(!que.empty()) que.pop(); memset(dist,0,sizeof(dist)); memset(vis,0,sizeof(vis)); vis[src]=true; que.push(src); while(!que.empty()){ int u=que.front();que.pop(); for(int i=g[u];i;i=e[i].nxt) if(e[i].f&&!vis[e[i].v]){ que.push(e[i].v); dist[e[i].v]=dist[u]+1; vis[e[i].v]=true; if(e[i].v==sink) return 1; } } return 0; } int dfs(int u,int delta) { if(u==sink) return delta; int ret=0; for(int i=g[u];ret<delta&&i;i=e[i].nxt) if(e[i].f&&dist[e[i].v]==dist[u]+1){ int dd=dfs(e[i].v,min(e[i].f,delta-ret)); if(dd>0){ e[i].f-=dd; e[i^1].f+=dd; ret+=dd; } else dist[e[i].v]=-1; } return ret; } int dinic() { int ret=0; while(bfs()==1) ret+=dfs(src,INT_MAX); return ret; } bool check(int mid) { init(); src=0,sink=n+1; for(int i=0;i<p;++i) if(c[i]<=mid) addedge(a[i],b[i],1); addedge(src,1,t); addedge(n,sink,t); if(dinic()==t) return true; return false; } int main() { scanf("%d%d%d",&n,&p,&t); int maxl=-1; for(int i=0;i<p;++i){ scanf("%d%d%d",&a[i],&b[i],&c[i]); maxl=max(maxl,c[i]); } int l=0,r=maxl+1,ans; while(l<r){ int mid=(l+r)/2; if(check(mid)) r=mid,ans=mid; else l=mid+1; } printf("%d",ans); return 0; }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。