題意：

題意：FJ有N塊地，這些地之間有P條雙向路，每條路的都有固定的長度l?，F(xiàn)在要你找出從第1塊地到第n塊地的T條不同路徑，每條路徑上的路不能與先前的路徑重復(fù)，問這些路徑中的最長路的最小是多少。

?

思路：二分答案+網(wǎng)絡(luò)流判定。
二分枚舉最大邊權(quán)，重新建圖，只保存權(quán)不超過最大邊權(quán)的邊。即如果邊的長度小于等于我們規(guī)定的最大邊權(quán) 則添加這條邊 權(quán)值為1， 否則標(biāo)記為0??

然后在網(wǎng)絡(luò)中起點(diǎn)終點(diǎn)間的容量是原圖中的路徑數(shù)，判斷最大流是否>=T

這里要注意的是，本題給的雙向邊，所以在添加反向弧時，容量應(yīng)該等于正向弧。

#include<iostream> #include<cstdio> #include<cstring> #include<queue> using namespace std;const int maxn = 205; const int INF = 0x3f3f3f3f; struct Edge {int from,to,next,w; }edge[2*maxn*maxn],E[maxn*maxn]; int n,m,cnt,head[maxn]; int level[maxn];void addedge(int u,int v,int w) {edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++;swap(u,v);edge[cnt].to = v;edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt++; }void build(int limit) {cnt = 0;memset(head,-1,sizeof(head));for(int i = 1; i <= m; i++)if(E[i].w <= limit)addedge(E[i].from,E[i].to,1); }int BFS(int src,int des){queue<int> q;memset(level,0,sizeof(level));level[src]=1;q.push(src);while(!q.empty()){int u = q.front();q.pop();if(u==des) return 1;for(int k = head[u];k!=-1;k=edge[k].next){int v = edge[k].to,w=edge[k].w;if(level[v]==0&&w!=0){level[v]=level[u]+1;q.push(v);}}}return -1; } int dfs(int u,int des,int increaseRoad){if(u==des) return increaseRoad;int ret=0;for(int k=head[u];k!=-1;k=edge[k].next){int v = edge[k].to, w = edge[k].w;if(level[v] == level[u] + 1 && w != 0){int MIN = min(increaseRoad-ret,w);w = dfs(v,des,MIN);if(w > 0){edge[k].w -=w;edge[k^1].w+=w;ret+=w;if(ret==increaseRoad) return ret;}else level[v] = -1; }}return ret; } int Dinic(int src,int des){int ans = 0;while(BFS(src,des)!=-1) ans+=dfs(src,des,INF);return ans; }int main() {int t;while(scanf("%d%d%d",&n,&m,&t)!=EOF){for(int i = 1; i <= m; i++)scanf("%d%d%d",&E[i].from,&E[i].to,&E[i].w);int l = 1, r = 1000000, mid,ans;while(l <= r){mid = (l + r) >> 1;build(mid);int tmp = Dinic(1,n);if(tmp >= t){ans = mid;r = mid - 1;}else l = mid + 1;}printf("%d\n",ans);}return 0; }

總結(jié)

以上是生活随笔為你收集整理的poj 2455 Secret Milking Machine(二分枚举+最大流)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。