Sending Secret Messages LightOJ

Sending Secret Messages LightOJ - 1404

Alice wants to send Bob some confidential messages. But their internet connection is not secured enough. As their names have been used in many networking schemes, they are very rich now. So, they don't want to send encoded messages, they want to use secured dedicated connection for them. So, they talked to some ISPS (Internet Service Providers) about their problem. Only they get is that there are N routers in the network, some of them share bidirectional links. Each link has a capacity, and for each KB of data passing through this link, they have to pay some money. Assume that Alice is connected with the 1^st router and Bob is connected to the N^th router.

For example, in the picture, Alice wants to send 4 KB data from router 1 to router 6. Each link is identified by two integers in the form (a, b) where 'a' denotes the capacity of the link and 'b'denotes per KB cost of the link. So, Alice can send 1KB of data through 1 - 2 - 3 - 4 - 6 (cost 8), 2KB data through 1 - 5 - 6 (cost 2 * 9=18) and 1KB data through 1 - 3 - 4 - 6 (cost 11). So, the total cost is 37 units.

Now Alice wants to send P KB of data to Bob. You have to find the minimum amount of money they have to pay to achieve their goal.

Input

Input starts with an integer T (≤ 50), denoting the number of test cases.

Each case starts with a blank line. Next line contains three integers N (2 ≤ N ≤ 50), M (0 ≤ M ≤ N*(N-1)/2) and P (1 ≤ P ≤ 1000), where M denotes the number of bidirectional links. Each of the next M lines contains four integers u v w c (1 ≤ u, v ≤ N, u ≠ v, 1 ≤ w, c ≤ 100), meaning that there is a link between router u and v, and at most c KB data can be sent through this link, and each KB of data through this link will cost w. You can assume that there will be at most one connection between a pair of routers.

Output

For each case, print the case number and the minimum amount of money required or "impossible" if it's not possible to send P KB of data.

Sample Input

6 9 4

3 1 9 8

1 2 1 2

1 5 6 1

5 6 2 8

6 4 2 2

4 2 7 6

2 6 7 9

3 4 5 1

3 2 2 3

6 9 9

3 1 9 8

1 2 1 2

1 5 6 1

5 6 2 8

6 4 2 2

4 2 7 6

2 6 7 9

3 4 5 1

3 2 2 3

4 4 20

1 3 1 3

3 4 1 4

1 2 1 2

2 4 1 5

Sample Output

Case 1: 37

Case 2: 139

Case 3: impossible

题意：给定一个图，有n个顶点m条无向边，每条边都有容量和费用，求从1到n穿输p的数据量时的费用。

题解：费用流模板，EK算法介绍 https://blog.csdn.net/y990041769/article/details/21026445

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 typedef long long ll;
  9 const int MAXX=60010;
 10 const int INF=0x3f3f3f3f;
 11 
 12 struct node
 13 {
 14     int st;
 15     int to;
 16     int next;
 17     int cap;
 18     int cost;
 19 }edge[MAXX];
 20 
 21 int head[MAXX],tol;
 22 int pre[MAXX],dis[MAXX];
 23 bool vis[MAXX];
 24 int n,m,p;
 25 
 26 void init()
 27 {
 28     tol=0;
 29     memset(head,-1,sizeof(head));
 30 }
 31 
 32 void addedge(int u,int v,int cap,int cost)
 33 {
 34     edge[tol].st=u;
 35     edge[tol].to=v;
 36     edge[tol].cap=cap;
 37     edge[tol].cost=cost;
 38     edge[tol].next=head[u];
 39     head[u]=tol++;
 40 
 41     edge[tol].st=v;
 42     edge[tol].to=u;
 43     edge[tol].cap=0;
 44     edge[tol].cost=-cost;
 45     edge[tol].next=head[v];
 46     head[v]=tol++;
 47 }
 48 
 49 int minCostMaxFlow(int s,int t,int p)
 50 {
 51     int cost=0;
 52     while(p>0)
 53     {
 54         queue<int> q;
 55         memset(dis,INF,sizeof(dis));
 56         memset(vis,0,sizeof(vis));
 57         memset(pre,-1,sizeof(pre));
 58         dis[s]=0;
 59         vis[s]=1;
 60         q.push(s);
 61         while(!q.empty())
 62         {
 63             int u=q.front(); q.pop();
 64             vis[u]=0;
 65             for(int i=head[u];i!=-1;i=edge[i].next)
 66             {
 67                 int to=edge[i].to;
 68                 if(edge[i].cap>0&&dis[to]>dis[u]+edge[i].cost)
 69                 {
 70                     dis[to]=dis[u]+edge[i].cost;
 71                     pre[to]=i;
 72                     if(!vis[to])
 73                     {
 74                         vis[to]=1;
 75                         q.push(to);
 76                     }
 77                 }
 78             }
 79         }
 80         if(dis[t]==INF)return -1;
 81         int minn=p;
 82 
 83         for(int i=pre[t];i!=-1;i=pre[edge[i].st])
 84             minn=min(minn,edge[i].cap);
 85 
 86         for(int i=pre[t];i!=-1;i=pre[edge[i].st])
 87         {
 88             edge[i].cap-=minn;
 89             edge[i^1].cap+=minn;
 90         }
 91         cost+=minn*dis[t];
 92         p-=minn;
 93     }
 94     return cost;
 95 }
 96 
 97 int main()
 98 {
 99     int T,x,y,z,w,cas=1;
100     scanf("%d",&T);
101     while(T--)
102     {
103         scanf("%d%d%d",&n,&m,&p);
104         init();
105         for(int i=1;i<=m;i++)
106         {
107             scanf("%d%d%d%d",&x,&y,&z,&w);
108             addedge(x,y,z,w);
109             addedge(y,x,z,w);
110         }
111         int ans=minCostMaxFlow(1,n,p);
112         printf("Case %d: ",cas++);
113         if(ans!=-1) printf("%d\n",ans);
114         else printf("impossible\n");
115     }
116     return 0;
117 }