首页 > 代码库 > NYIST 1006 偷西瓜
NYIST 1006 偷西瓜
偷西瓜
时间限制：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”.
- 样例输入
211 2 999331 3 102 1 203 2 50
- 样例输出
eating80
- 上传者
- 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 long14 #define pii pair<int,int>15 #define INF 0x3f3f3f3f16 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 }
NYIST 1006 偷西瓜
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。