偷西瓜

時間限制：1000?ms ?|? 內存限制：65535?KB 難度：4 描述

對于農村的孩子來說最大的樂趣，莫過于和小伙伴們一塊下地偷西瓜了，雖然孩子們條件不是很好，但是往往他們很聰明，他們總在計算著到達瓜田的距離，以及逃跑的路線，他們總是以最短的距離沖到瓜田里面，然后以最短的距離回到出發的地方，不過瓜田的大人們已經在他們來的路上等待他們。于是聰明的小伙伴們便不走過的路，即每條路只走一遍,如果小伙伴們回不到出發的地方，他們就說“eating”，

我們假設?有?n?(n<=100)個?村莊?m條路(m<=1000)小伙伴們總是從1號村莊出發，而瓜田總是在n號村莊.如果小伙伴們到達不了n號村莊，或者回不到1號村莊請輸出"eating";

輸入

多組數據
第一行一個整數 n?
第二行 一個整數 m
隨后的m行 有 三個數u,v,w 表示u 到 v村莊的距離為w(w<=1000);

輸出

求小伙伴們從1號村莊出發，到 n號村莊，再回到1號村莊所用的最短距離，如果不能回到1號村莊請輸出“eating”.

樣例輸入

2 1 1 2 999 3 3 1 3 10 2 1 20 3 2 50

樣例輸出

eating 80

上傳者

ACM_王亞龍

?

解題：費用流。。。

1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define pii pair<int,int> 15 #define INF 0x3f3f3f3f 16 using namespace std; 17 const int maxn = 110; 18 struct arc{ 19 int to,flow,cost,next; 20 arc(int x = 0,int y = 0,int z = 0,int nxt = -1){ 21 to = x; 22 flow = y; 23 cost = z; 24 next = nxt; 25 } 26 }; 27 arc e[maxn*maxn]; 28 int head[maxn],d[maxn],p[maxn],tot,n,m,S,T; 29 void add(int u,int v,int flow,int cost){ 30 e[tot] = arc(v,flow,cost,head[u]); 31 head[u] = tot++; 32 e[tot] = arc(u,0,-cost,head[v]); 33 head[v] = tot++; 34 } 35 bool spfa(){ 36 queue<int>q; 37 bool in[maxn] = {false}; 38 for(int i = S; i <= T; ++i) p[i] = -1,d[i] = INF; 39 d[S] = 0; 40 q.push(S); 41 while(!q.empty()){ 42 int u = q.front(); 43 q.pop(); 44 in[u] = false; 45 for(int i = head[u]; ~i; i = e[i].next){ 46 if(e[i].flow && d[e[i].to] > d[u] + e[i].cost){ 47 d[e[i].to] = d[u] + e[i].cost; 48 p[e[i].to] = i; 49 if(!in[e[i].to]) { 50 in[e[i].to] = true; 51 q.push(e[i].to); 52 } 53 } 54 } 55 } 56 return p[T] > -1; 57 } 58 bool solve(int &ans){ 59 int flow = ans = 0; 60 while(spfa()){ 61 int minFlow = INF; 62 for(int i = p[T]; ~i; i = p[e[i^1].to]) 63 minFlow = min(e[i].flow,minFlow); 64 for(int i = p[T]; ~i; i = p[e[i^1].to]){ 65 e[i].flow -= minFlow; 66 e[i^1].flow += minFlow; 67 } 68 flow += minFlow; 69 ans += d[T]*minFlow; 70 } 71 return flow == 2; 72 } 73 int main() { 74 while(~scanf("%d %d",&n,&m)){ 75 tot = S = 0; 76 T = n + 1; 77 int u,v,w; 78 memset(head,-1,sizeof(head)); 79 for(int i = 0; i < m; ++i){ 80 scanf("%d %d %d",&u,&v,&w); 81 add(u,v,1,w); 82 add(v,u,1,w); 83 } 84 add(S,1,2,0); 85 add(n,T,2,0); 86 int ans; 87 if(solve(ans)) printf("%d\n",ans); 88 else puts("eating"); 89 } 90 return 0; 91 } View Code

?

轉載于:https://www.cnblogs.com/crackpotisback/p/4052082.html

總結

以上是生活随笔為你收集整理的NYIST 1006 偷西瓜的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。