COGS 运输问题4 (费用流)

【问题描述】

一个工厂每天生产若干商品，需运输到销售部门进行销售。从产地到销地要经过某些城镇，有不同的路线可以行走，每条两城镇间的公路都有一定的流量限制。公路设有收费站，每通过一辆车，要交纳过路费。请你计算，在不考虑其它车辆使用公路的前提下，如何使产地运输到销地的商品最多，并使费用最少。

【输入格式】

输入文件有若干行
第一行，一个整数n，表示共有n个城市

第二行，一个整数，表示起点城市

第三行，一个整数，表示终点城市
下面有n行,每行有

【输出格式】

输出文件有一行
第一行，1个整数n，表示最小费用为n。

【输入输出样例】

输入文件名： maxflowd.in

6
1
6
0 0 1 3 5 10 0 0 0 0 0 0
0 0 0 0 0 0 5 7 0 0 0 0
0 0 0 0 0 0 0 0 2 8 0 0
0 0 0 0 1 3 0 0 0 0 3 5
0 0 2 4 0 0 0 0 0 0 2 6
0 0 0 0 0 0 0 0 0 0 0 0

输出文件名：maxflowd.out

  1 /*
  2     裸裸的模板 
  3 */
  4 #include <ctype.h> 
  5 #include <cstdio>
  6 
  7 const int MAXN_EDGE=100010; 
  8 const int MAXN=1010;
  9 const int INF=0x7fffffff;
 10 
 11 struct State {
 12     int to;
 13     int next;
 14     int cost;
 15     int val;
 16 };
 17 State w[MAXN_EDGE];
 18 
 19 int head[MAXN],tot=1;
 20 
 21 int n,s,t,src,decc;
 22 
 23 int qu[MAXN],dis[MAXN],fee[MAXN],vis[MAXN],pre[MAXN];
 24 
 25 inline void read(int&x) {
 26     register char c=getchar();
 27     for(x=0;!isdigit(c);c=getchar());
 28     for(;isdigit(c);x=x*10+c-48,c=getchar());
 29 }
 30 
 31 inline void add(int x,int y,int val,int fee) {
 32     w[++tot].to=y;
 33     w[tot].cost=fee;
 34     w[tot].val=val;
 35     w[tot].next=head[x];
 36     head[x]=tot;
 37 }
 38 
 39 inline int min(int x,int y) {return x<y?x:y;}
 40 
 41 bool SPFA() {
 42     int hea=0,tail=1;
 43     for(int i=src;i<=decc;++i) vis[i]=0,dis[i]=INF,fee[i]=INF,pre[i]=-1;
 44     qu[tail]=src;
 45     dis[src]=0;
 46     vis[src]=1;
 47     while(hea<tail) {
 48         int u=qu[++hea];
 49         vis[u]=0;
 50         for(int i=head[u];i!=-1;i=w[i].next) {
 51             int to=w[i].to;
 52             if(w[i].val&&dis[to]>dis[u]+w[i].cost) {
 53                 dis[to]=dis[u]+w[i].cost;
 54                 fee[to]=min(fee[u],w[i].val);
 55                 pre[to]=i;
 56                 if(!vis[to]) {
 57                     qu[++tail]=to;
 58                     vis[to]=1;
 59                 }
 60             }
 61         }
 62     }
 63     return dis[decc]!=INF;
 64 }
 65 
 66 inline int change() {
 67     for(int i=pre[decc];i!=-1;i=pre[w[i^1].to]) {
 68         w[i].val-=fee[decc];
 69         w[i^1].val+=fee[decc];
 70     }
 71     return fee[decc]*dis[decc];
 72 }
 73 
 74 inline int ISPA() {
 75     int ans=0;
 76     while(SPFA()) 
 77       ans+=change();
 78     return ans;
 79 }
 80 
 81 int hh() {
 82     freopen("maxflowd.in","r",stdin);
 83     freopen("maxflowd.out","w",stdout);
 84     int x,y;
 85     read(n);read(s);read(t); 
 86     decc=n+1;
 87     for(int i=0;i<=2*n+1;++i) head[i]=-1;
 88     for(int i=1;i<=n;++i)
 89       for(int j=1;j<=2*n;j+=2) {
 90           read(x);read(y);
 91           int J=(j+1)/2;
 92           if(x) add(i,J,x,y),add(J,i,0,-y);
 93       }
 94     add(src,s,INF,0),add(s,src,0,0);
 95     add(t,decc,INF,0),add(decc,t,0,0);
 96     printf("%d
",ISPA());
 97     return 0;
 98 }
 99 
100 int sb=hh();
101 int main() {;}

代码

作者：乌鸦坐飞机
出处：http://www.cnblogs.com/whistle13326/
新的风暴已经出现怎么能够停止不前穿越时空竭尽全力我会来到你身边微笑面对危险梦想成真不会遥远鼓起勇气坚定向前奇迹一定会出现