[关闭]
@ivorysi 2018-01-02T08:43:54.000000Z 字数 45353 阅读 769

网络流学习笔记

笔记

POJ 3041 Asteroids

Description

Bessie wants to navigate her spaceship through a dangerous asteroid field in the shape of an N x N grid (1 <= N <= 500). The grid contains K asteroids (1 <= K <= 10,000), which are conveniently located at the lattice points of the grid.
Fortunately, Bessie has a powerful weapon that can vaporize all the asteroids in any given row or column of the grid with a single shot.This weapon is quite expensive, so she wishes to use it sparingly.Given the location of all the asteroids in the field, find the minimum number of shots Bessie needs to fire to eliminate all of the asteroids.

Input

  • Line 1: Two integers N and K, separated by a single space.
  • Lines 2..K+1: Each line contains two space-separated integers R and C (1 <= R, C <= N) denoting the row and column coordinates of an asteroid, respectively.

Output

  • Line 1: The integer representing the minimum number of times Bessie must shoot.

Sample Input

3 4
1 1
1 3
2 2
3 2

Sample Output

2

Hint

INPUT DETAILS:

The following diagram represents the data, where "X" is an asteroid and "." is empty space:
X.X
.X.
.X.
OUTPUT DETAILS:
Bessie may fire across row 1 to destroy the asteroids at (1,1) and (1,3), and then she may fire down column 2 to destroy the asteroids at (2,2) and (3,2).

题解

每一行作为一个点，每一列作为一个点，原点向每一行连一个容量为1的边，如果有X，该行向该列连一个容量为边的点，每一列向汇点连一条容量为1的边
也就是……二分图匹配的网络流版本吧

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 1005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  29. struct node {
  30.     int to,next,val;
  31. }edge[100005];
  32. int head[MAXN],sumedge=1,dis[MAXN],gap[MAXN];
  33. bool usedrow[MAXN],usedcol[MAXN];
  34. int nodecnt;
  35. void add(int u,int v,int c) {
  36.     edge[++sumedge].to=v;
  37.     edge[sumedge].next=head[u];
  38.     edge[sumedge].val=c;
  39.     head[u]=sumedge;
  40. }
  41. void addtwo(int u,int v,int c) {
  42.     add(u,v,c);
  43.     add(v,u,0);
  44. }
  45. int sap(int u,int aug) {
  46.     int flow=0,dmin=nodecnt-1;
  47.     if(u==nodecnt) {
  48.         return aug;
  49.     }
  50.     for(int i=head[u];i;i=edge[i].next) {
  51.         if(edge[i].val>0) {
  52.             int v=edge[i].to;
  53.             if(dis[v]+1==dis[u]) {
  54.                 int t=sap(v,min(edge[i].val,aug-flow));
  55.                 flow+=t;
  56.                 edge[i].val-=t;
  57.                 edge[i^1].val+=t;
  58.                 if(flow==aug) return flow;
  59.                 if(dis[1]>=nodecnt) return flow; 
  60.             }
  61.             dmin=min(dmin,dis[v]);
  62.         }
  63.     }
  64.     if(!flow) {
  65.         gap[dis[u]]--;
  66.         if(gap[dis[u]]==0) {dis[u]=nodecnt;return flow;}
  67.         dis[u]=dmin+1;
  68.         gap[dis[u]]++;
  69.     }
  70.     return flow;
  71. }
  72. int n,k,r,c,ans;
  73. void solve() {
  74.     n=read();
  75.     k=read();
  76.     siji(i,1,k) {
  77.         r=read();c=read();
  78.         usedrow[r]=1;usedcol[c]=1;
  79.         addtwo(r+1,c+n+1,1);
  80.     }
  81.     nodecnt=2*n+2;
  82.     siji(i,1,n) {
  83.         if(usedrow[i]) addtwo(1,i+1,1);
  84.         if(usedcol[i]) addtwo(i+n+1,nodecnt,1);
  85.     }
  86.     while(dis[1]<nodecnt) ans+=sap(1,0x7fffffff);
  87.     printf("%d\n",ans);
  88. }
  89. int main() {
  90. #ifdef ivorysi
  91.     freopen("f1.in","r",stdin);
  92. #endif
  93.     solve();
  94. }

Evacuation

Description

Fires can be disastrous, especially when a fire breaks out in a room that is completely filled with people. Rooms usually have a couple of exits and emergency exits, but with everyone rushing out at the same time, it may take a while for everyone to escape.
You are given the floorplan of a room and must find out how much time it will take for everyone to get out. Rooms consist of obstacles and walls, which are represented on the map by an 'X', empty squares, represented by a '.' and exit doors, which are represented by a 'D'. The boundary of the room consists only of doors and walls, and there are no doors inside the room. The interior of the room contains at least one empty square.
Initially, there is one person on every empty square in the room and these persons should move to a door to exit. They can move one square per second to the North, South, East or West. While evacuating, multiple persons can be on a single square. The doors are narrow, however, and only one person can leave through a door per second.
What is the minimal time necessary to evacuate everybody? A person is evacuated at the moment he or she enters a door square.

Input

The first line of the input contains a single number: the number of test cases to follow. Each test case has the following format:
One line with two integers Y and X, separated by a single space, satisfying 3 <= Y, X <= 12: the size of the room
Y lines with X characters, each character being either 'X', '.', or 'D': a valid description of a room

Output

For every test case in the input, the output should contain a single line with the minimal evacuation time in seconds, if evacuation is possible, or "impossible", if it is not.

Sample Input

3
5 5
XXDXX
X...X
D...X
X...D
XXXXX
5 12
XXXXXXXXXXXX
X..........D
X.XXXXXXXXXX
X..........X
XXXXXXXXXXXX
5 5
XDXXX
X.X.D
XX.XX
D.X.X
XXXDX

Sample Output

3
21
impossible

题解

我们对于每个门，宽搜一遍周围的点到它的距离，注意不能走门，有可能一个门被另一个门挡住
然后按照时间加边，看看什么时候流完

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <queue>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MAXN 1005
  12. #define mod 1000000007
  13. #define pii pair<int,int>
  14. #define fi first
  15. #define se second
  16. //#define ivorysi
  17. using namespace std;
  18. typedef long long ll;
  19. ll read() {
  20.     ll res=0,neg=1;
  21.     char c=getchar();
  22.     while(c<'0' || c>'9') {
  23.     if(c=='-') neg=-1;
  24.     c=getchar();
  25.     }
  26.     while(c>='0' && c<='9') {
  27.     res=res*10+c-'0';
  28.     c=getchar();
  29.     }
  30.     return res*neg;
  31. }
  33. struct node {
  34.     int to,next,val;
  35. }edge[MAXN*1000];
  36. int head[MAXN],sumedge=1,sink,source,dis[MAXN],gap[MAXN];
  37. int dx[]={0,1,0,-1};
  38. int dy[]={1,0,-1,0};
  39. void add(int u,int v,int c) {
  40.     edge[++sumedge].to=v;
  41.     edge[sumedge].next=head[u];
  42.     edge[sumedge].val=c;
  43.     head[u]=sumedge;
  44. }
  45. void addtwo(int u,int v,int c) {
  46.     add(u,v,c);
  47.     add(v,u,0);
  48. }
  49. int T,n,m;
  50. int away[25][25];
  51. char map[25][25];
  52. bool alive[25][25],inq[25][25];
  53. vector<int> pos[MAXN],dist[MAXN];
  54. int sap(int u,int aug) {
  55.     if(u==sink) {
  56.         return aug;
  57.     }
  58.     int flow=0,dmin=sink-1;
  59.     for(int i=head[u];i;i=edge[i].next) {
  60.         if(edge[i].val>0) {
  61.             int v=edge[i].to;
  62.             if(dis[v]+1==dis[u]) {
  63.                 int t=sap(v,min(edge[i].val,aug-flow));
  64.                 flow+=t;
  65.                 edge[i].val-=t;
  66.                 edge[i^1].val+=t;
  67.                 if(flow==aug) return flow;
  68.                 if(dis[source]==sink) return flow;
  69.             }
  70.             dmin=min(dis[v],dmin);
  71.         }
  72.     }
  73.     if(!flow) {
  74.         --gap[dis[u]];
  75.         if(gap[dis[u]]==0) {dis[source]=sink;return flow;}
  76.         dis[u]=dmin+1;
  77.         ++gap[dis[u]];
  78.     }
  79.     return flow;
  80. }
  81. inline int calc(int a,int b) {
  82.     return (a-1)*m+b+1;
  83. }
  84. queue<pii> q;
  85. void bfs(int a,int b) {
  86.     alive[a][b]=1;
  87.     memset(inq,0,sizeof(inq));
  88.     inq[a][b]=1;
  89.     memset(away,0,sizeof(away));
  90.     q.push(make_pair(a,b));
  91.     while(!q.empty()) {
  92.         pii now=q.front();q.pop();
  93.         siji(i,0,3) {
  94.             if(map[now.fi+dx[i]][now.se+dy[i]]=='.') {
  95.                 if(!inq[now.fi+dx[i]][now.se+dy[i]]) {
  96.                     inq[now.fi+dx[i]][now.se+dy[i]]=1;
  97.                     alive[now.fi+dx[i]][now.se+dy[i]]=1;
  98.                     away[now.fi+dx[i]][now.se+dy[i]]=away[now.fi][now.se]+1;
  99.                     pos[calc(a,b)].push_back(calc(now.fi+dx[i],now.se+dy[i]));
  100.                     dist[calc(a,b)].push_back(away[now.fi][now.se]+1);
  101.                     q.push(make_pair(now.fi+dx[i],now.se+dy[i]));
  102.                 }
  103.             }
  104.         }
  105.     }
  106. }
  108. void connect(int ti) {
  109.     memset(dis,0,sizeof(dis));
  110.     memset(gap,0,sizeof(gap));
  111.     siji(i,1,n) {
  112.         siji(j,1,m) {
  113.             if(map[i][j]=='D') {
  114.                 addtwo(calc(i,j),sink,1);
  115.                 int s=pos[calc(i,j)].size();
  116.                 xiaosiji(k,0,s) {
  117.                     if(dist[calc(i,j)][k]==ti) {
  118.                         addtwo(pos[calc(i,j)][k],calc(i,j),0x7fffffff);
  119.                     }
  120.                 }
  121.             }
  123.         }
  124.     }
  125. }
  127. void solve() {
  128.     memset(head,0,sizeof(head));
  129.     sumedge=1;
  130.     n=read();m=read();
  131.     siji(i,1,n) {
  132.         scanf("%s",map[i]+1);
  133.     }
  134.     siji(i,0,n) map[i][m+1]=map[i][0]='X';
  135.     siji(j,0,m) map[0][j]=map[n+1][j]='X';
  136.     source=1;sink=n*m+2;
  137.     int Z=0;
  138.     memset(alive,0,sizeof(alive));
  139.     siji(i,1,n) {
  140.         siji(j,1,m) {
  141.             dist[calc(i,j)].clear();
  142.             pos[calc(i,j)].clear();
  143.             if(map[i][j]=='X') continue;
  144.             if(map[i][j]=='.') {
  145.                 ++Z;
  146.                 addtwo(source,calc(i,j),1);
  147.             }
  148.             if(map[i][j]=='D') {
  149.                 bfs(i,j);
  150.             }
  151.         }
  152.     }
  153.     siji(i,1,n) {
  154.         siji(j,1,m) {
  155.             if(map[i][j]=='.' && (!alive[i][j])) {
  156.                 puts("impossible");
  157.                 return;
  158.             }
  159.         }
  160.     }
  161.     int L=0;
  162.     while(Z>0) {
  163.         ++L;
  164.         connect(L);
  165.         int res=0;
  166.         while(dis[source]<sink) res+=sap(source,Z);
  167.         Z-=res;
  169.     }
  170.     printf("%d\n",L);
  171. }
  172. int main() {
  173. #ifdef ivorysi
  174.     freopen("f1.in","r",stdin);
  175. #endif
  176.     T=read();
  177.     while(T--) {
  178.         solve();
  179.     }
  180. }

POJ 1149 PIGS

PIGS

Description

Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day.

Input

The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0.

Output

The first and only line of the output should contain the number of sold pigs.

Sample Input

3 3
3 1 10
2 1 2 2
2 1 3 3
1 2 6

Sample Output

7

题解

题目简单翻译一下
有m个猪圈，n个人
m个猪圈里有一些猪
n个人手里有a个猪圈的钥匙，每个人可以打开对应的猪圈，每个人需要b头猪，作为猪圈管理者可以选择将一些猪买给他们，但是个数不能超过b
每个人打开猪圈门后，这时作为管理者你可以重新调整每个猪圈中猪的个数
已知这n份订单，请问最多能卖出多少头猪
这道题可以发现
he can redistribute the remaining pigs across the unlocked pig-houses.
暗示我们每个人来之后状态会发生变化，也就是时间是一个重要的关键字
那么建模的思路就很明显了，按照时间拆点
原点向第一个人来之前的猪圈连一条容量为猪的个数的边，然后再将第一个人可以打开的猪圈连到第一个人身上，然后这个人向汇点连一条容量为买猪的个数的边
下一个时刻是上一个时刻里的那个人能打开的门之间互相连边，例如第一个人来了打开了1号门和2号门
那么第一个时刻的1号门向第二个时刻的2号门连一条容量为正无穷的边，第一个时刻的2号门向第二个时刻的1号门连一条容量为正无穷的边，
之后……第一个时刻的1号门向第二个时刻的1号门连一条容量为正无穷的边，第一个时刻的2号门向第二个时刻的2号门连一条容量为正无穷的边，第一个时刻的3号门向第二个时刻的3号门连一条容量为正无穷的边
然后再将第二个带的钥匙和第二个时刻的猪圈联系起来
以此类推
虽然是一次过的但是de了很久，因为一开始写成if(i!=1) 然后向从上一个时刻向该时刻转移，没有注意到我读入的猪圈是这个人可以打开的，应该是从第一个人可以打开的猪圈开始向下一个时刻转移，边界条件是if(i!=n)

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  8. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  9. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  10. #define MAXN 1000005
  11. #define mod 1000000007
  12. //#define ivorysi
  13. using namespace std;
  14. typedef long long ll;
  15. ll read() {
  16.     ll res=0,neg=1;
  17.     char c=getchar();
  18.     while(c<'0' || c>'9') {
  19.     if(c=='-') neg=-1;
  20.     c=getchar();
  21.     }
  22.     while(c>='0' && c<='9') {
  23.     res=res*10+c-'0';
  24.     c=getchar();
  25.     }
  26.     return res*neg;
  27. }
  28. struct node {
  29.     int to,next,val;
  30. }edge[MAXN*50];
  31. int head[MAXN*2],sumedge=1,dis[MAXN*2],gap[MAXN*2],source,sink;
  32. int m,n;
  33. int a[1005],num;
  34. void add(int u,int v,int c) {
  35.     edge[++sumedge].to=v;
  36.     edge[sumedge].next=head[u];
  37.     edge[sumedge].val=c;
  38.     head[u]=sumedge;
  39. }
  40. void addtwo(int u,int v,int c) {
  41.     add(u,v,c);
  42.     add(v,u,0);
  43. }
  44. int sap(int u,int aug) {
  45.     if(u==sink) return aug;
  46.     int flow=0,dmin=sink-1;
  47.     for(int i=head[u];i;i=edge[i].next) {
  48.     if(edge[i].val>0) {
  49.         int v=edge[i].to;
  50.         if(dis[v]+1==dis[u]) {
  51.         int t=sap(v,min(edge[i].val,aug-flow));
  52.         flow+=t;
  53.         edge[i].val-=t;
  54.         edge[i^1].val+=t;
  55.         if(flow==aug) return flow;
  56.         if(dis[source]==sink) return flow;
  57.         }
  58.         dmin=min(dis[v],dmin);
  59.     }
  60.     }
  61.     if(!flow) {
  62.     --gap[dis[u]];
  63.     if(gap[dis[u]]==0) {dis[source]=sink;return 0;}
  64.     dis[u]=dmin+1;
  65.     gap[dis[u]]++;
  66.     }
  67.     return flow;
  68. }
  70. void solve() {
  71.     m=read();
  72.     n=read();
  73.     source=1;
  74.     sink=n*m+n+2;
  75.     int l;
  76.     siji(i,1,m) {
  77.     l=read();
  78.     addtwo(source,i+1,l);
  79.     }
  80.     int b;
  81.     siji(i,1,n) {
  82.     num=read();
  83.     siji(j,1,num) {
  84.         a[j]=read();
  85.         addtwo(m*(i-1)+a[j]+1,n*m+1+i,0x7fffffff);
  86.     }
  87.     if(i!=n) {
  88.         siji(j,1,num) {
  89.         siji(k,1,num) {
  90.             if(a[k]!=a[j]) {
  91.             addtwo(m*(i-1)+a[j]+1,m*i+a[k]+1,0x7fffffff);
  92.             }
  93.         }
  95.         }
  96.         siji(j,1,m) addtwo(m*(i-1)+j+1,m*i+j+1,0x7fffffff);
  97.     }
  98.     b=read();
  99.     addtwo(n*m+i+1,sink,b);
  100.     }
  101.     int ans=0;
  102.     while(dis[source]<sink) ans+=sap(source,0x7fffffff);
  103.     printf("%d\n",ans);
  104. }
  105. int main() {
  106. #ifdef ivorysi
  107.     freopen("f1.in","r",stdin);
  108. #endif
  109.     solve();
  110. }

POJ 3281 Dining

Description

Cows are such finicky eaters. Each cow has a preference for certain foods and drinks, and she will consume no others.
Farmer John has cooked fabulous meals for his cows, but he forgot to check his menu against their preferences. Although he might not be able to stuff everybody, he wants to give a complete meal of both food and drink to as many cows as possible.
Farmer John has cooked F (1 ≤ F ≤ 100) types of foods and prepared D (1 ≤ D ≤ 100) types of drinks. Each of his N (1 ≤ N ≤ 100) cows has decided whether she is willing to eat a particular food or drink a particular drink. Farmer John must assign a food type and a drink type to each cow to maximize the number of cows who get both.
Each dish or drink can only be consumed by one cow (i.e., once food type 2 is assigned to a cow, no other cow can be assigned food type 2).

Input

Line 1: Three space-separated integers: N, F, and D
Lines 2..N+1: Each line i starts with a two integers Fi and Di, the number of dishes that cow i likes and the number of drinks that cow i likes. The next Fi integers denote the dishes that cow i will eat, and the Di integers following that denote the drinks that cow i will drink.

Output

Line 1: A single integer that is the maximum number of cows that can be fed both food and drink that conform to their wishes

Sample Input

4 3 3
2 2 1 2 3 1
2 2 2 3 1 2
2 2 1 3 1 2
2 1 1 3 3

Sample Output

3

Hint

One way to satisfy three cows is:
Cow 1: no meal
Cow 2: Food #2, Drink #2
Cow 3: Food #1, Drink #1
Cow 4: Food #3, Drink #3
The pigeon-hole principle tells us we can do no better since there are only three kinds of food or drink. Other test data sets are more challenging, of course.

题解

我原来觉得是二分图匹配，但是如果一头牛有很多种搭配，二分图匹配的话可能会用到很多边来自一头牛
所以我们需要网络流来限流
牛拆成了两个点
原点向食物连一条容量为1的边，食物向牛1连一条容量为1的边，牛1向牛2连一条容量为1的边，牛2向饮料连一条容量为1的边，饮料向汇点连一条容量为1的边

题解

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 1005
  13. #define esp 1e-8
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  18. struct node {
  19.     int to,next,val;
  20. }edge[MAXN*10];
  21. int head[MAXN*10],sumedge=1;
  22. int n,f,d,source,sink;
  23. void add(int u,int v,int c) {
  24.     edge[++sumedge].val=c;
  25.     edge[sumedge].to=v;
  26.     edge[sumedge].next=head[u];
  27.     head[u]=sumedge;
  28. }
  29. void addtwo(int u,int v,int c) {
  30.     add(u,v,c);
  31.     add(v,u,0);
  32. }
  33. int dis[MAXN],gap[MAXN];
  34. int sap(int u,int aug) {
  35.     if(u==sink) return aug;
  36.     int flow=0,dmin=sink-1;
  37.     for(int i=head[u];i;i=edge[i].next) {
  38.     int v=edge[i].to;
  39.     if(edge[i].val>0) {
  40.         if(dis[v]+1==dis[u]) {
  41.         int t=sap(v,min(edge[i].val,aug-flow));
  42.         flow+=t;
  43.         edge[i].val-=t;
  44.         edge[i^1].val+=t;
  45.         if(flow==aug) return flow;
  46.         if(dis[source]>=sink) return flow;
  47.         }
  48.         dmin=min(dmin,dis[v]);
  49.     }
  50.     }
  51.     if(!flow) {
  52.     gap[dis[u]]--;
  53.     if(gap[dis[u]]==0) dis[source]=sink;
  54.     dis[u]=dmin+1;
  55.     gap[dis[u]]++;
  56.     }
  57.     return flow;
  58. }
  59. void solve() {
  60.     scanf("%d%d%d",&n,&f,&d);
  61.     source=1;
  62.     sink=(n*2+f+d+2);
  63.     siji(i,1,f) {
  64.     addtwo(source,i+1,1);
  65.     }
  66.     siji(i,1,d) {
  67.     addtwo(i+f+1,sink,1);
  68.     }
  69.     int tf,td,x;
  70.     siji(i,1,n) {
  71.     scanf("%d%d",&tf,&td);
  72.     addtwo(1+f+d+i*2-1,1+f+d+i*2,1);
  73.     siji(j,1,tf) {
  74.         scanf("%d",&x);
  75.         addtwo(x+1,1+f+d+i*2-1,1);
  76.     }
  77.     siji(j,1,td) {
  78.         scanf("%d",&x);
  79.         addtwo(1+f+d+i*2,1+f+x,1);
  80.     }
  81.     }
  82.     int ans=0;
  83.     while(dis[source]<sink) {
  84.     ans+=sap(source,0x7fffffff);
  85.     }
  86.     printf("%d\n",ans);
  87. }
  88. int main() {
  89. #ifdef ivorysi
  90.     freopen("f1.in","r",stdin);
  91. #endif
  92.     solve();
  93.     return 0;
  95. }

POJ 3469 Dual Core CPU

Description

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.
The routine consists of N modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let's define them as Ai and Bi. Meanwhile, M pairs of modules need to do some data-exchange. If they are running on the same core, then the cost of this action can be ignored. Otherwise, some extra cost are needed. You should arrange wisely to minimize the total cost.

Input

There are two integers in the first line of input data, N and M (1 ≤ N ≤ 20000, 1 ≤ M ≤ 200000) .
The next N lines, each contains two integer, Ai and Bi.
In the following M lines, each contains three integers: a, b, w. The meaning is that if module a and module b don't execute on the same core, you should pay extra w dollars for the data-exchange between them.

Output

Output only one integer, the minimum total cost.

Sample Input

3 1
1 10
2 10
10 3
2 3 1000

Sample Output

13

题解

这道题有点像2-sat
每个任务拆成两个点，一个是在A核上完成，一个是在B核上完成
原点向在A核上完成任务连一条容量为ai的边，B核上完成任务向汇点连一条容量为bi的边
这两个点之间连一条容量为正无穷的边
然后我们对于约束条件，在x的A核完成向在y的B核完成连一条容量为w的边，y的B核到x的A核也连一条边
在x的B核完成向在y的A核完成连一条容量为w的边，y的A核到x的B核也连一条边

这样在，选A核，选B核，选罚款之间我们会选择最小的流到汇点
当我们选择了不同的核后，它们的罚款一定会通过另一个核流到终点

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 200005
  13. #define MAXM 2000005
  14. #define esp 1e-8
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  19. struct node {
  20.     int to,next,val;
  21. }edge[MAXM];
  22. int head[MAXN*2],sumedge=1,source,sink;
  23. void add(int u,int v,int c) {
  24.     edge[++sumedge].to=v;
  25.     edge[sumedge].val=c;
  26.     edge[sumedge].next=head[u];
  27.     head[u]=sumedge;
  28. }
  29. void addtwo(int u,int v,int c) {
  30.     add(u,v,c);
  31.     add(v,u,0);
  32. }
  33. int dis[MAXN*2],gap[MAXN*2];
  34. int sap(int u,int aug) {
  35.     if(u==sink) return aug;
  36.     int dmin=sink-1,flow=0;
  37.     for(int i=head[u];i;i=edge[i].next) {
  38.     int v=edge[i].to;
  39.     if(edge[i].val>0) {
  40.         if(dis[v]+1==dis[u]) {
  41.         int t=sap(v,min(edge[i].val,aug-flow));
  42.         edge[i].val-=t;
  43.         edge[i^1].val+=t;
  44.         flow+=t;
  45.         if(flow==aug) return flow;
  46.         if(dis[source]>=sink) return flow;
  47.         }
  48.         dmin=min(dmin,dis[v]);
  49.     }
  50.     }
  51.     if(!flow) {
  52.     --gap[dis[u]];
  53.     if(gap[dis[u]]==0) dis[source]=sink;
  54.     dis[u]=dmin+1;
  55.     gap[dis[u]]++;
  56.     }
  57.     return flow;
  58. }
  59. int n,m;
  60. void solve() {
  61.     scanf("%d%d",&n,&m);
  62.     int a,b,w;
  63.     source=1;
  64.     sink=n*2+2;
  65.     siji(i,1,n) {
  66.     scanf("%d%d",&a,&b);
  67.     addtwo(source,i+1,a);
  68.     addtwo(i+n+1,sink,b);
  69.     addtwo(i+1,i+n+1,0x7fffffff);
  70.     }
  71.     siji(i,1,m) {
  72.     scanf("%d%d%d",&a,&b,&w);
  73.     addtwo(a+1,b+n+1,w);
  74.     addtwo(b+n+1,a+1,w);
  75.     addtwo(b+1,a+n+1,w);
  76.     addtwo(a+n+1,b+1,w);
  77.     }
  78.     int ans=0;
  79.     while(dis[source]<sink) {
  80.     ans+=sap(source,0x7fffffff);
  81.     }
  82.     printf("%d\n",ans);
  83. }
  84. int main() {
  85. #ifdef ivorysi
  86.     freopen("f1.in","r",stdin);
  87. #endif
  88.     solve();
  89.     return 0;
  91. }

POJ 2987 Firing

Description

You’ve finally got mad at “the world’s most stupid” employees of yours and decided to do some firings. You’re now simply too mad to give response to questions like “Don’t you think it is an even more stupid decision to have signed them?”, yet calm enough to consider the potential profit and loss from firing a good portion of them. While getting rid of an employee will save your wage and bonus expenditure on him, termination of a contract before expiration costs you funds for compensation. If you fire an employee, you also fire all his underlings and the underlings of his underlings and those underlings’ underlings’ underlings… An employee may serve in several departments and his (direct or indirect) underlings in one department may be his boss in another department. Is your firing plan ready now?

Input

The input starts with two integers n (0 < n ≤ 5000) and m (0 ≤ m ≤ 60000) on the same line. Next follows n + m lines. The first n lines of these give the net profit/loss from firing the i-th employee individually bi (|bi| ≤ 107, 1 ≤ i ≤ n). The remaining m lines each contain two integers i and j (1 ≤ i, j ≤ n) meaning the i-th employee has the j-th employee as his direct underling.

Output

Output two integers separated by a single space: the minimum number of employees to fire to achieve the maximum profit, and the maximum profit.

Sample Input

5 5
8
-9
-20
12
-10
1 2
2 5
1 4
3 4
4 5

Sample Output

2 2

Hint

As of the situation described by the sample input, firing employees 4 and 5 will produce a net profit of 2, which is maximum.

题解

这道题我们需要学习最大权闭合子图
最大权闭合子图包括一个点集，这个点集里所有点的出边指向的点都在这个点集里
如何求解呢，网上有很多很好的博客，我简单的记录一下

将所有边的容量改成正无穷，从原点向每个权值为正的点连一条容量为权值的边
将每个权值为负的点向汇点连一条容量为权值绝对值的边
那么这样的话我们在这个图上跑一个最大流，获得的最大流的值是x，那么最大权闭合图的最大权就是：
所有正数点权的权值和-x

这样的话我们对于题里的图这样建图，可以求出最大收益，然后按照残余网络搜索到的点的个数就是我们需要裁员的个数

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 50005
  13. #define MAXM 600005
  14. #define esp 1e-8
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  19. struct node {
  20.     int to,next;
  21.     ll val;
  22. }edge[MAXM];
  23. int head[MAXN*2],sumedge=1,source,sink;
  24. void add(int u,int v,ll c) {
  25.     edge[++sumedge].to=v;
  26.     edge[sumedge].val=c;
  27.     edge[sumedge].next=head[u];
  28.     head[u]=sumedge;
  29. }
  30. void addtwo(int u,int v,ll c) {
  31.     add(u,v,c);
  32.     add(v,u,0);
  33. }
  34. int dis[MAXN*2],gap[MAXN*2];
  35. ll sap(int u,ll aug) {
  36.     if(u==sink) return aug;
  37.     int dmin=sink-1;ll flow=0;
  38.     for(int i=head[u];i;i=edge[i].next) {
  39.     int v=edge[i].to;
  40.     if(edge[i].val>0) {
  41.         if(dis[v]+1==dis[u]) {
  42.         ll t=sap(v,min(edge[i].val,aug-flow));
  43.         edge[i].val-=t;
  44.         edge[i^1].val+=t;
  45.         flow+=t;
  46.         if(flow==aug) return flow;
  47.         if(dis[source]>=sink) return flow;
  48.         }
  49.         dmin=min(dmin,dis[v]);
  50.     }
  51.     }
  52.     if(!flow) {
  53.     --gap[dis[u]];
  54.     if(gap[dis[u]]==0) dis[source]=sink;
  55.     dis[u]=dmin+1;
  56.     gap[dis[u]]++;
  57.     }
  58.     return flow;
  59. }
  60. int n,m;
  61. bool used[MAXN];
  62. ll val[MAXN];
  63. ll maxval,all;
  64. void dfs(int u) {
  65.     used[u]=1;
  66.     for(int i=head[u];i;i=edge[i].next) {
  67.     int v=edge[i].to;
  68.     if(!used[v] && edge[i].val>0) {
  69.         dfs(v);
  70.     }
  71.     }
  72. }
  73. void solve() {
  74.     scanf("%d%d",&n,&m);
  75.     maxval=(ll)5005*10000000;
  76.     source=1,sink=n+2;
  77.     siji(i,1,n) {
  78.     scanf("%lld",&val[i]);
  79.     if(val[i]>0) {
  80.         addtwo(source,i+1,val[i]);
  81.         all+=val[i];
  82.     }
  83.     else if(val[i]<0) {
  84.         addtwo(i+1,sink,-val[i]);
  85.     }
  86.     }
  87.     int a,b;
  88.     siji(i,1,m) {
  89.     scanf("%d%d",&a,&b);
  90.     addtwo(a+1,b+1,maxval);
  91.     }
  92.     ll ans=0;
  93.     while(dis[source]<sink) {
  94.     ans+=sap(source,maxval);
  95.     }
  96.     ans=all-ans;
  97.     dfs(source);
  98.     int person=0;
  99.     siji(i,2,n+1) {
  100.     if(used[i]) ++person; 
  101.     }
  102.     printf("%d %lld\n",person,ans);
  103. }
  104. int main() {
  105. #ifdef ivorysi
  106.     freopen("f1.in","r",stdin);
  107. #endif
  108.     solve();
  109.     return 0;
  111. }

POJ 3155 Hard Life

Description

John is a Chief Executive Officer at a privately owned medium size company. The owner of the company has decided to make his son Scott a manager in the company. John fears that the owner will ultimately give CEO position to Scott if he does well on his new manager position, so he decided to make Scott’s life as hard as possible by carefully selecting the team he is going to manage in the company.
John knows which pairs of his people work poorly in the same team. John introduced a hardness factor of a team — it is a number of pairs of people from this team who work poorly in the same team divided by the total number of people in the team. The larger is the hardness factor, the harder is this team to manage. John wants to find a group of people in the company that are hardest to manage and make it Scott’s team. Please, help him.
In the example on the picture the hardest team consists of people 1, 2, 4, and 5. Among 4 of them 5 pairs work poorly in the same team, thus hardness factor is equal to 5⁄4. If we add person number 3 to the team then hardness factor decreases to 6⁄5.

Input

The first line of the input file contains two integer numbers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 1000). Here n is a total number of people in the company (people are numbered from 1 to n), and m is the number of pairs of people who work poorly in the same team. Next m lines describe those pairs with two integer numbers ai and bi (1 ≤ ai, bi ≤ n, ai ≠ bi) on a line. The order of people in a pair is arbitrary and no pair is listed twice.

Output

Write to the output file an integer number k (1 ≤ k ≤ n) — the number of people in the hardest team, followed by k lines listing people from this team in ascending order. If there are multiple teams with the same hardness factor then write any one.

Sample Input

sample input #1

5 6
1 5
5 4
4 2
2 5
1 2
3 1

sample input #2

4 0

Sample Output

sample output #1

4
1
2
4
5

sample output #2

1
1

Hint

Note, that in the last example any team has hardness factor of zero, and any non-empty list of people is a valid answer.

题解

我们要考虑最大密度子图
这怎么办呢，我们还需要想一下我们的01分数规划
我们二分一个小数
设边数为e，节点数为v

设
我们将所有边抽象成一个点，这个点权值为1，原来的点每个点权值为-g，然和建图，跑一遍最大权闭合子图，就是答案
和我们二分到的g比较
判断解是否合法

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 105
  13. #define MAXM 1005
  14. #define esp 1e-8
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. bool dcmp(double a,double b) {
  19.     return fabs(b-a)<=esp;
  20. }
  21. struct node {
  22.     int to,next;
  23.     double val;
  24. }edge[MAXM*100];
  25. int head[MAXN+MAXM],sumedge=1,source,sink;
  26. int U[MAXM],V[MAXM],n,m;
  27. void add(int u,int v,double c) {
  28.     edge[++sumedge].to=v;
  29.     edge[sumedge].val=c;
  30.     edge[sumedge].next=head[u];
  31.     head[u]=sumedge;
  32. }
  33. void addtwo(int u,int v,double c) {
  34.     add(u,v,c);
  35.     add(v,u,0);
  36. }
  37. int dis[MAXN+MAXM],gap[MAXN+MAXM];
  38. double sap(int u,double aug) {
  39.     if(u==sink) return aug;
  40.     int dmin=sink-1;double flow=0;
  41.     for(int i=head[u];i;i=edge[i].next) {
  42.     int v=edge[i].to;
  43.     if(edge[i].val>esp) {
  44.         if(dis[v]+1==dis[u]) {
  45.         double t=sap(v,min(edge[i].val,aug-flow));
  46.         edge[i].val-=t;
  47.         edge[i^1].val+=t;
  48.         flow+=t;
  49.         if(flow==aug) return flow;
  50.         if(dis[source]>=sink) return flow;
  51.         }
  52.         dmin=min(dmin,dis[v]);
  53.     }
  54.     }
  55.     if(!flow) {
  56.     --gap[dis[u]];
  57.     if(gap[dis[u]]==0) dis[source]=sink;
  58.     dis[u]=dmin+1;
  59.     gap[dis[u]]++;
  60.     }
  61.     return flow;
  62. }
  63. bool check(double mid) {
  64.     sumedge=1;
  65.     memset(head,0,sizeof(head));
  66.     memset(dis,0,sizeof(dis));
  67.     memset(gap,0,sizeof(gap));
  68.     siji(i,1,m) {
  69.     addtwo(1+n+i,U[i]+1,(double)m);
  70.     addtwo(1+n+i,V[i]+1,(double)m);
  71.     }
  72.     siji(i,1,n) {addtwo(i+1,sink,mid);}
  73.     siji(i,1,m) {addtwo(source,1+n+i,1);}
  74.     double ans=(double)m;
  75.     while(dis[source]<sink) {
  76.     ans-=sap(source,(double)m);
  77.     }
  78.     return ans>=esp;
  79. }
  80. bool used[MAXM+MAXN];
  81. vector<int> v;
  82. void dfs(int u) {
  83.     used[u]=1;
  84.     for(int i=head[u];i;i=edge[i].next) {
  85.     int v=edge[i].to;
  86.     if(!used[v] && !dcmp(edge[i].val,0.0)) {
  87.         dfs(v);
  88.     }
  89.     }
  90. }
  91. void solve() {
  92.     scanf("%d%d",&n,&m);
  93.     siji(i,1,m) {
  94.     scanf("%d%d",&U[i],&V[i]);
  95.     }
  96.     source=1;sink=m+n+2;
  97.     double l=0,r=m;
  98.     while(r-l > 1e-5) {
  99.     double mid=(l+r)/2.0;
  100.     if(check(mid)) l=mid;
  101.     else r=mid;
  102.     }
  103.     check(l);
  104.     dfs(source);
  105.     siji(i,1,n) {
  106.     if(used[i+1]) {
  107.         v.push_back(i);
  108.     }
  109.     }
  110.     if(v.size()==0) v.push_back(1);
  111.     sort(v.begin(),v.end());
  112.     int s=v.size();
  113.     printf("%d\n",s);
  114.     xiaosiji(i,0,s) {
  115.     printf("%d\n",v[i]);
  116.     }
  117. }
  118. int main() {
  119. #ifdef ivorysi
  120.     freopen("f1.in","r",stdin);
  121. #endif
  122.     solve();
  123.     return 0;
  125. }

费用流

Farm Tour

Description

When FJ's friends visit him on the farm, he likes to show them around. His farm comprises N (1 <= N <= 1000) fields numbered 1..N, the first of which contains his house and the Nth of which contains the big barn. A total M (1 <= M <= 10000) paths that connect the fields in various ways. Each path connects two different fields and has a nonzero length smaller than 35,000.
To show off his farm in the best way, he walks a tour that starts at his house, potentially travels through some fields, and ends at the barn. Later, he returns (potentially through some fields) back to his house again.
He wants his tour to be as short as possible, however he doesn't want to walk on any given path more than once. Calculate the shortest tour possible. FJ is sure that some tour exists for any given farm.

Input

  • Line 1: Two space-separated integers: N and M.
  • Lines 2..M+1: Three space-separated integers that define a path: The starting field, the end field, and the path's length.

Output

A single line containing the length of the shortest tour.

Sample Input

4 5
1 2 1
2 3 1
3 4 1
1 3 2
2 4 2

Sample Output

6

题解

https://artofproblemsolving.com/community/h1020435
写了一发zkw费用流
十分好写比spfa增广还好写
简单记录一下思路网络流还是暴力地流，而我们用KM的重标记（mark一下我现在并不知道KM是什么）我们每次找到起点被流到而终点却没有的最小的一条边，加上它的花费，然后再在每条边上减去这些花费，直到不能再找到一条边去更新为止
更新标记大概就是从当前集合扩展出去的边里选一个最小的，所以必然会多出一条当前的最短路
这里的优化在于它没有用最短路算法，而是靠单纯的修改编号
最短路图必然满足的是我们把所有边都减去当前的最小花费d，那么这条性质并不会改变，并且多了一条新边进入这个图，可以用于增广，同时我们还要将他们的对边花费加上d，这样使得退流的时候同时退掉花费

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 1005
  13. #define MAXM 10005
  14. #define esp 1e-8
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  18. bool dcmp(double a,double b) {
  19.     return fabs(b-a)<=esp;
  20. }
  21. struct node {
  22.     int to,next,val,cost;
  23. }edge[MAXM*10];
  24. int n,m;
  25. int head[MAXN*2],sumedge=1,sink,source;
  26. bool vis[MAXN*2];
  27. void add(int u,int v,int l,int c) {
  28.     edge[++sumedge].to=v;
  29.     edge[sumedge].next=head[u];
  30.     edge[sumedge].val=l;
  31.     edge[sumedge].cost=c;
  32.     head[u]=sumedge;
  33. }
  34. void addtwo(int u,int v,int l,int c) {
  35.     add(u,v,l,c);
  36.     add(v,u,0,-c);
  37. }
  38. int pi1=0,ans;
  39. int aug(int u,int all) {
  40.     if(u==sink) {
  41.     ans+=all*pi1;
  42.     return all;
  43.     }
  44.     int flow=0;
  45.     vis[u]=1;
  46.     for(int i=head[u];i;i=edge[i].next) {
  47.     int v=edge[i].to;
  48.     if(edge[i].cost==0 && edge[i].val>0 && !vis[v]) {
  49.         int t=aug(v,min(edge[i].val,all-flow));
  50.         flow+=t;
  51.         edge[i].val-=t;
  52.         edge[i^1].val+=t;
  53.         if(flow==all) return flow;
  54.     }
  55.     }
  56.     return flow;
  57. }
  58. bool modlabel() {
  59.     int d=0x7fffffff;
  60.     siji(u,source,sink) {
  61.     if(vis[u]) {
  62.         for(int i=head[u];i;i=edge[i].next) {
  63.         int v=edge[i].to;
  64.         if(edge[i].val>0 && !vis[v] && edge[i].cost<d) d=edge[i].cost;
  65.         }
  66.     }
  67.     }
  68.     if(d==0x7fffffff) return false;
  69.     siji(u,source,sink) {
  70.     if(vis[u]) {
  71.         for(int i=head[u];i;i=edge[i].next) {
  72.         edge[i].cost-=d;edge[i^1].cost+=d;
  73.         }
  74.     }
  75.     }
  76.     pi1+=d;
  77.     return true;
  78. }
  79. void solve() {
  80.     scanf("%d%d",&n,&m);
  81.     int u,v,c;
  82.     sink=n+2,source=1;
  83.     addtwo(source,2,2,0);
  84.     addtwo(n+1,sink,2,0);
  85.     siji(i,1,m) {
  86.         scanf("%d%d%d",&u,&v,&c);
  87.         addtwo(u+1,v+1,1,c);
  88.         addtwo(v+1,u+1,1,c);
  89.     }
  90.     do {
  91.         do {
  92.             memset(vis,0,sizeof(vis));
  93.         }while(aug(source,0x7fffffff));
  94.     }while(modlabel());
  95.     printf("%d\n",ans);
  96. }
  97. int main() {
  98. #ifdef ivorysi
  99.     freopen("f1.in","r",stdin);
  100. #endif
  101.     solve();
  102.     return 0;
  104. }

POJ 3686 The Windy's

Description

The Windy's is a world famous toy factory that owns M top-class workshop to make toys. This year the manager receives N orders for toys. The manager knows that every order will take different amount of hours in different workshops. More precisely, the i-th order will take Zij hours if the toys are making in the j-th workshop. Moreover, each order's work must be wholly completed in the same workshop. And a workshop can not switch to another order until it has finished the previous one. The switch does not cost any time.
The manager wants to minimize the average of the finishing time of the N orders. Can you help him?

Input

The first line of input is the number of test case. The first line of each test case contains two integers, N and M (1 ≤ N,M ≤ 50).
The next N lines each contain M integers, describing the matrix Zij (1 ≤ Zij ≤ 100,000) There is a blank line before each test case.

Output

For each test case output the answer on a single line. The result should be rounded to six decimal places.

Sample Input

3
3 4
100 100 100 1
99 99 99 1
98 98 98 1
3 4
1 100 100 100
99 1 99 99
98 98 1 98
3 4
1 100 100 100
1 99 99 99
98 1 98 98

Sample Output

2.000000
1.000000
1.333333

题解

这道题大概还是要应用按时间拆点的思想吧
我们每个订单建一个点，每个工厂拆成n个点，表示的是工厂倒数处理了第几个玩具
因为如果工厂处理了k个玩具
那么
a1,a1+a2,a1+a2+a3……
那么总共的时间就是
k*a1+(k-1)*a2+(k-2)*a3……
那么每个订单向某一个工厂拆成的第k个点连一条容量为1，权值为k×z[i][j]的边
原点向订单连一条容量为1，费用为0的边
工厂的n×m个点向汇点连一条容量为1，费用为0的边

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 3005
  13. #define MAXM 10005
  14. #define esp 1e-8
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  20. int n,m;
  21. int z[55][55];
  22. int source,sink;
  23. struct node {
  24.     int to,next,cap,cost;
  25. }edge[3000005];
  26. int head[MAXN],sumedge,pi1,ans;
  27. void add(int u,int v,int l,int c) {
  28.     edge[++sumedge].to=v;
  29.     edge[sumedge].next=head[u];
  30.     edge[sumedge].cap=l;
  31.     edge[sumedge].cost=c;
  32.     head[u]=sumedge;
  33. }
  34. void addtwo(int u,int v,int l,int c) {
  35.     add(u,v,l,c);
  36.     add(v,u,0,-c);
  37. }
  38. bool vis[MAXN];
  39. int aug(int u,int stream) {
  40.     if(u==sink) {
  41.     ans+=pi1*stream;
  42.     return stream;
  43.     }
  44.     vis[u]=1;
  45.     int flow=0;
  46.     for(int i=head[u];i;i=edge[i].next) {
  47.     int v=edge[i].to;
  48.     if(!vis[v] && edge[i].cap>0 && edge[i].cost==0) {
  49.         int t=aug(v,min(stream-flow,edge[i].cap));
  50.         flow+=t;
  51.         edge[i].cap-=t;
  52.         edge[i^1].cap+=t;
  53.     }
  54.     }
  55.     return flow;
  56. }
  57. bool modlabel() {
  58.     int d=0x7fffffff;
  59.     siji(u,source,sink) {
  60.     if(vis[u]) {
  61.         for(int i=head[u];i;i=edge[i].next) {
  62.         int v=edge[i].to;
  63.         if(!vis[v] && edge[i].cap>0 && d>edge[i].cost) {
  64.             d=edge[i].cost;
  65.         }
  66.         }
  67.     } 
  68.     }
  69.     if(d==0x7fffffff) return false;
  70.     siji(u,source,sink) {
  71.     if(vis[u]) {
  72.         for(int i=head[u];i;i=edge[i].next) {
  73.         edge[i].cost-=d;
  74.         edge[i^1].cost+=d;
  75.         }
  76.     }
  77.     }
  78.     pi1+=d;
  79.     return true;
  80. }
  81. void solve() {
  82.     scanf("%d%d",&n,&m);
  83.     memset(head,0,sizeof(head));
  84.     ans=0;
  85.     pi1=0;
  86.     sumedge=1;
  87.     source=1;
  88.     sink=n+n*m+2;
  89.     siji(i,1,n) {
  90.     siji(j,1,m) {
  91.         scanf("%d",&z[i][j]);
  92.         addtwo(n+1+(i-1)*m+j,sink,1,0);
  93.     }
  94.     }
  96.     siji(i,1,n) {
  97.     addtwo(source,i+1,1,0);
  98.     }
  99.     siji(i,1,n) {
  100.     siji(j,1,m) {
  101.         siji(k,1,n) {
  102.         addtwo(i+1,n+1+(k-1)*m+j,1,z[i][j]*k);
  103.         }
  104.     }
  105.     }
  106.     do {
  107.     do {
  108.         memset(vis,0,sizeof(vis));
  109.     }while(aug(source,n));
  110.     }while(modlabel());
  111.     printf("%.6lf\n",(double)ans/n);
  112. }
  113. int main() {
  114. #ifdef ivorysi
  115.     freopen("f1.in","r",stdin);
  116. #endif
  117.     int T;
  118.     scanf("%d",&T);
  119.     while(T--) {
  120.     solve();
  121.     }
  122.     return 0;
  124. }

POJ 3068 "Shortest" pair of paths

Description

A chemical company has an unusual shortest path problem.
There are N depots (vertices) where chemicals can be stored. There are M individual shipping methods (edges) connecting pairs of depots. Each individual shipping method has a cost. In the usual problem, the company would need to find a way to route a single shipment from the first depot (0) to the last (N - 1). That's easy. The problem they have seems harder. They have to ship two chemicals from the first depot (0) to the last (N - 1). The chemicals are dangerous and cannot safely be placed together. The regulations say the company cannot use the same shipping method for both chemicals. Further, the company cannot place the two chemicals in same depot (for any length of time) without special storage handling --- available only at the first and last depots. To begin, they need to know if it's possible to ship both chemicals under these constraints. Next, they need to find the least cost of shipping both chemicals from first depot to the last depot. In brief, they need two completely separate paths (from the first depot to the last) where the overall cost of both is minimal.
Your program must simply determine the minimum cost or, if it's not possible, conclusively state that the shipment cannot be made.

Input

The input will consist of multiple cases. The first line of each input will contain N and M where N is the number of depots and M is the number of individual shipping methods. You may assume that N is less than 64 and that M is less than 10000. The next M lines will contain three values, i, j, and v. Each line corresponds a single, unique shipping method. The values i and j are the indices of two depots, and v is the cost of getting from i to j. Note that these shipping methods are directed. If something can be shipped from i to j with cost 10, that says nothing about shipping from j to i. Also, there may be more than one way to ship between any pair of depots, and that may be important here.
A line containing two zeroes signals the end of data and should not be processed.

Output

follow the output format of sample output.

Sample Input

2 1
0 1 20
2 3
0 1 20
0 1 20
1 0 10
4 6
0 1 22
1 3 11
0 2 14
2 3 26
0 3 43
0 3 58
0 0

Sample Output

Instance #1: Not possible
Instance #2: 40
Instance #3: 73

题解

和上面的某个板题似乎没什么区别

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 3005
  13. #define MAXM 10005
  14. #define esp 1e-8
  15. //#define ivorysi
  16. using namespace std;
  17. typedef long long ll;
  20. int n,m;
  21. int source,sink;
  22. struct node {
  23.     int to,next,cap,cost;
  24. }edge[3000005];
  25. int head[MAXN],sumedge,pi1,ans;
  26. void add(int u,int v,int l,int c) {
  27.     edge[++sumedge].to=v;
  28.     edge[sumedge].next=head[u];
  29.     edge[sumedge].cap=l;
  30.     edge[sumedge].cost=c;
  31.     head[u]=sumedge;
  32. }
  33. void addtwo(int u,int v,int l,int c) {
  34.     add(u,v,l,c);
  35.     add(v,u,0,-c);
  36. }
  37. bool vis[MAXN];
  38. int aug(int u,int stream) {
  39.     if(u==sink) {
  40.     ans+=pi1*stream;
  41.     return stream;
  42.     }
  43.     vis[u]=1;
  44.     int flow=0;
  45.     for(int i=head[u];i;i=edge[i].next) {
  46.     int v=edge[i].to;
  47.     if(!vis[v] && edge[i].cap>0 && edge[i].cost==0) {
  48.         int t=aug(v,min(stream-flow,edge[i].cap));
  49.         flow+=t;
  50.         edge[i].cap-=t;
  51.         edge[i^1].cap+=t;
  52.     }
  53.     }
  54.     return flow;
  55. }
  56. bool modlabel() {
  57.     int d=0x7fffffff;
  58.     siji(u,source,sink) {
  59.     if(vis[u]) {
  60.         for(int i=head[u];i;i=edge[i].next) {
  61.         int v=edge[i].to;
  62.         if(!vis[v] && edge[i].cap>0 && d>edge[i].cost) {
  63.             d=edge[i].cost;
  64.         }
  65.         }
  66.     } 
  67.     }
  68.     if(d==0x7fffffff) return false;
  69.     siji(u,source,sink) {
  70.     if(vis[u]) {
  71.         for(int i=head[u];i;i=edge[i].next) {
  72.         edge[i].cost-=d;
  73.         edge[i^1].cost+=d;
  74.         }
  75.     }
  76.     }
  77.     pi1+=d;
  78.     return true;
  79. }
  80. void solve() {
  81.     memset(head,0,sizeof(head));
  82.     ans=0;
  83.     pi1=0;
  84.     sumedge=1;
  85.     source=1;
  86.     sink=n+2;
  87.     int u,v,c;
  88.     addtwo(source,2,2,0);
  89.     siji(i,1,m) {
  90.     scanf("%d%d%d",&u,&v,&c);
  91.     addtwo(u+2,v+2,1,c);
  92.     }
  93.     addtwo(n+1,sink,2,0);
  94.     int tmp=0,x;
  95.     do {
  96.     do {
  97.         memset(vis,0,sizeof(vis));
  98.         x=aug(source,2);
  99.         tmp+=x;
  100.     }while(x);
  101.     }while(modlabel());
  102.     if(tmp!=2) {
  103.     puts("Not possible");
  104.     }
  105.     else {
  106.     printf("%d\n",ans);
  107.     }
  108. }
  109. int main() {
  110. #ifdef ivorysi
  111.     freopen("f1.in","r",stdin);
  112. #endif
  113.     int T=0;
  114.     while(scanf("%d%d",&n,&m)!=EOF) {
  115.     if(n==0 && m==0) break;
  116.     ++T;
  117.     printf("Instance #%d: ",T);
  118.     solve();
  119.     }
  121.     return 0;
  122. }

POJ 2195 Going Home

Description

On a grid map there are n little men and n houses. In each unit time, every little man can move one unit step, either horizontally, or vertically, to an adjacent point. For each little man, you need to pay a $1 travel fee for every step he moves, until he enters a house. The task is complicated with the restriction that each house can accommodate only one little man.
Your task is to compute the minimum amount of money you need to pay in order to send these n little men into those n different houses. The input is a map of the scenario, a '.' means an empty space, an 'H' represents a house on that point, and am 'm' indicates there is a little man on that point.
You can think of each point on the grid map as a quite large square, so it can hold n little men at the same time; also, it is okay if a little man steps on a grid with a house without entering that house.

Input

There are one or more test cases in the input. Each case starts with a line giving two integers N and M, where N is the number of rows of the map, and M is the number of columns. The rest of the input will be N lines describing the map. You may assume both N and M are between 2 and 100, inclusive. There will be the same number of 'H's and 'm's on the map; and there will be at most 100 houses. Input will terminate with 0 0 for N and M.

Output

For each test case, output one line with the single integer, which is the minimum amount, in dollars, you need to pay.

Sample Input

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

Sample Output

2
10
28

题解

格子拆点，向四周的格子连边，容量为n，费用为1
原点向有人的点连一条容量为1费用为0的边
房子向汇点连一条容量为1费用为0的边

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 105
  13. #define esp 1e-8
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  19. int n,m;
  20. int source,sink;
  21. struct node {
  22.     int to,next,cap,cost;
  23. }edge[4000005];
  24. int head[MAXN*MAXN],sumedge,pi1,ans;
  25. char map[MAXN][MAXN];
  26. void add(int u,int v,int l,int c) {
  27.     edge[++sumedge].to=v;
  28.     edge[sumedge].next=head[u];
  29.     edge[sumedge].cap=l;
  30.     edge[sumedge].cost=c;
  31.     head[u]=sumedge;
  32. }
  33. void addtwo(int u,int v,int l,int c) {
  34.     add(u,v,l,c);
  35.     add(v,u,0,-c);
  36. }
  37. bool vis[MAXN*MAXN];
  38. int aug(int u,int stream) {
  39.     if(u==sink) {
  40.     ans+=pi1*stream;
  41.     return stream;
  42.     }
  43.     vis[u]=1;
  44.     int flow=0;
  45.     for(int i=head[u];i;i=edge[i].next) {
  46.     int v=edge[i].to;
  47.     if(!vis[v] && edge[i].cap>0 && edge[i].cost==0) {
  48.         int t=aug(v,min(stream-flow,edge[i].cap));
  49.         flow+=t;
  50.         edge[i].cap-=t;
  51.         edge[i^1].cap+=t;
  52.     }
  53.     }
  54.     return flow;
  55. }
  56. bool modlabel() {
  57.     int d=0x7fffffff;
  58.     siji(u,source,sink) {
  59.     if(vis[u]) {
  60.         for(int i=head[u];i;i=edge[i].next) {
  61.         int v=edge[i].to;
  62.         if(!vis[v] && edge[i].cap>0 && d>edge[i].cost) {
  63.             d=edge[i].cost;
  64.         }
  65.         }
  66.     } 
  67.     }
  68.     if(d==0x7fffffff) return false;
  69.     siji(u,source,sink) {
  70.     if(vis[u]) {
  71.         for(int i=head[u];i;i=edge[i].next) {
  72.         edge[i].cost-=d;
  73.         edge[i^1].cost+=d;
  74.         }
  75.     }
  76.     }
  77.     pi1+=d;
  78.     return true;
  79. }
  80. void solve() {
  81.     memset(head,0,sizeof(head));
  82.     ans=0;
  83.     pi1=0;
  84.     sumedge=1;
  85.     source=1;
  86.     sink=n*m+2;
  87.     siji(i,1,n) {
  88.     scanf("%s",map[i]+1);
  89.     siji(j,1,m) {
  90.         if(map[i][j]=='m') {
  91.         addtwo(source,(i-1)*m+j+1,1,0);
  92.         }
  93.         if(map[i][j]=='H') {
  94.         addtwo((i-1)*m+j+1,sink,1,0);
  95.         }
  96.         if(i!=1) addtwo((i-1)*m+j+1,(i-2)*m+j+1,n,1);
  97.         if(i!=n) addtwo((i-1)*m+j+1,i*m+j+1,n,1);
  98.         if(j!=1) addtwo((i-1)*m+j+1,(i-1)*m+j,n,1);
  99.         if(j!=m) addtwo((i-1)*m+j+1,(i-1)*m+j+2,n,1);
  100.     }
  101.     }
  102.     do {
  103.     do {
  104.         memset(vis,0,sizeof(vis));
  105.     }while(aug(source,n));
  106.     }while(modlabel());
  107.     printf("%d\n",ans);
  108. }
  109. int main() {
  110. #ifdef ivorysi
  111.     freopen("f1.in","r",stdin);
  112. #endif
  113.     int T=0;
  114.     while(scanf("%d%d",&n,&m)!=EOF) {
  115.     if(n==0 && m==0) break;
  116.     solve();
  117.     }
  119.     return 0;
  120. }

POJ 3422 Kaka's Matrix Travels

Description

On an N × N chessboard with a non-negative number in each grid, Kaka starts his matrix travels with SUM = 0. For each travel, Kaka moves one rook from the left-upper grid to the right-bottom one, taking care that the rook moves only to the right or down. Kaka adds the number to SUM in each grid the rook visited, and replaces it with zero. It is not difficult to know the maximum SUM Kaka can obtain for his first travel. Now Kaka is wondering what is the maximum SUM he can obtain after his Kth travel. Note the SUM is accumulative during the K travels.

Input

The first line contains two integers N and K (1 ≤ N ≤ 50, 0 ≤ K ≤ 10) described above. The following N lines represents the matrix. You can assume the numbers in the matrix are no more than 1000.

Output

The maximum SUM Kaka can obtain after his Kth travel.

Sample Input

3 2
1 2 3
0 2 1
1 4 2

Sample Output

15

题解

这道题实际上是传纸条的一般形式（误）
由于我们的算法是跑最小费用，那么我们可以用1000-val[i][j]作为值，然后跑费用流
把每个点拆成一条边来记录点权值

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define MAXN 105
  13. #define esp 1e-8
  14. //#define ivorysi
  15. using namespace std;
  16. typedef long long ll;
  19. int n,k;
  20. int source,sink;
  21. struct node {
  22.     int to,next,cap,cost;
  23. }edge[4000005];
  24. int head[MAXN*MAXN],sumedge,pi1,ans;
  25. int st[MAXN][MAXN],ed[MAXN][MAXN],sumnode=0;
  26. int val[MAXN][MAXN];
  27. void add(int u,int v,int l,int c) {
  28.     edge[++sumedge].to=v;
  29.     edge[sumedge].next=head[u];
  30.     edge[sumedge].cap=l;
  31.     edge[sumedge].cost=c;
  32.     head[u]=sumedge;
  33. }
  34. void addtwo(int u,int v,int l,int c) {
  35.     add(u,v,l,c);
  36.     add(v,u,0,-c);
  37. }
  38. bool vis[MAXN*MAXN];
  39. int aug(int u,int stream) {
  40.     if(u==sink) {
  41.     ans+=pi1*stream;
  42.     return stream;
  43.     }
  44.     vis[u]=1;
  45.     int flow=0;
  46.     for(int i=head[u];i;i=edge[i].next) {
  47.     int v=edge[i].to;
  48.     if(!vis[v] && edge[i].cap>0 && edge[i].cost==0) {
  49.         int t=aug(v,min(stream-flow,edge[i].cap));
  50.         flow+=t;
  51.         edge[i].cap-=t;
  52.         edge[i^1].cap+=t;
  53.     }
  54.     }
  55.     return flow;
  56. }
  57. bool modlabel() {
  58.     int d=0x7fffffff;
  59.     siji(u,source,sink) {
  60.     if(vis[u]) {
  61.         for(int i=head[u];i;i=edge[i].next) {
  62.         int v=edge[i].to;
  63.         if(!vis[v] && edge[i].cap>0 && d>edge[i].cost) {
  64.             d=edge[i].cost;
  65.         }
  66.         }
  67.     } 
  68.     }
  69.     if(d==0x7fffffff) return false;
  70.     siji(u,source,sink) {
  71.     if(vis[u]) {
  72.         for(int i=head[u];i;i=edge[i].next) {
  73.         edge[i].cost-=d;
  74.         edge[i^1].cost+=d;
  75.         }
  76.     }
  77.     }
  78.     pi1+=d;
  79.     return true;
  80. }
  81. void solve() {
  82.     memset(head,0,sizeof(head));
  83.     ans=0;
  84.     pi1=0;
  85.     sumedge=1;
  86.     source=1;
  87.     sumnode=1;
  88.     scanf("%d%d",&n,&k);
  89.     siji(i,1,n) {
  90.     siji(j,1,n) {
  91.         scanf("%d",&val[i][j]);
  92.         st[i][j]=++sumnode;
  93.         ed[i][j]=++sumnode;
  94.         addtwo(st[i][j],ed[i][j],1,1000-val[i][j]);
  95.         addtwo(st[i][j],ed[i][j],k-1,1000);
  96.         if(i!=1) {
  97.         addtwo(ed[i-1][j],st[i][j],k,0);
  98.         }
  99.         if(j!=1) {
  100.         addtwo(ed[i][j-1],st[i][j],k,0);
  101.         }
  102.     }
  103.     }
  105.     addtwo(source,st[1][1],k,0);
  106.     sink=++sumnode;
  107.     addtwo(ed[n][n],sink,k,0);
  108.     do {
  109.     do {
  110.         memset(vis,0,sizeof(vis));
  111.     }while(aug(source,k));
  112.     }while(modlabel());
  113.     printf("%d\n",(2*n-1)*k*1000-ans);
  114. }
  115. int main() {
  116. #ifdef ivorysi
  117.     freopen("f1.in","r",stdin);
  118. #endif
  119.     solve();
  120.     return 0;
  121. }

POJ 2175 Evacuation Plan

Description

The City has a number of municipal buildings and a number of fallout shelters that were build specially to hide municipal workers in case of a nuclear war. Each fallout shelter has a limited capacity in terms of a number of people it can accommodate, and there's almost no excess capacity in The City's fallout shelters. Ideally, all workers from a given municipal building shall run to the nearest fallout shelter. However, this will lead to overcrowding of some fallout shelters, while others will be half-empty at the same time.
To address this problem, The City Council has developed a special evacuation plan. Instead of assigning every worker to a fallout shelter individually (which will be a huge amount of information to keep), they allocated fallout shelters to municipal buildings, listing the number of workers from every building that shall use a given fallout shelter, and left the task of individual assignments to the buildings' management. The plan takes into account a number of workers in every building - all of them are assigned to fallout shelters, and a limited capacity of each fallout shelter - every fallout shelter is assigned to no more workers then it can accommodate, though some fallout shelters may be not used completely.
The City Council claims that their evacuation plan is optimal, in the sense that it minimizes the total time to reach fallout shelters for all workers in The City, which is the sum for all workers of the time to go from the worker's municipal building to the fallout shelter assigned to this worker.
The City Mayor, well known for his constant confrontation with The City Council, does not buy their claim and hires you as an independent consultant to verify the evacuation plan. Your task is to either ensure that the evacuation plan is indeed optimal, or to prove otherwise by presenting another evacuation plan with the smaller total time to reach fallout shelters, thus clearly exposing The City Council's incompetence.
During initial requirements gathering phase of your project, you have found that The City is represented by a rectangular grid. The location of municipal buildings and fallout shelters is specified by two integer numbers and the time to go between municipal building at the location (Xi, Yi) and the fallout shelter at the location (Pj, Qj) is Di,j = |Xi - Pj| + |Yi - Qj| + 1 minutes.

Input

The input consists of The City description and the evacuation plan description. The first line of the input file consists of two numbers N and M separated by a space. N (1 ≤ N ≤ 100) is a number of municipal buildings in The City (all municipal buildings are numbered from 1 to N). M (1 ≤ M ≤ 100) is a number of fallout shelters in The City (all fallout shelters are numbered from 1 to M).
The following N lines describe municipal buildings. Each line contains there integer numbers Xi, Yi, and Bi separated by spaces, where Xi, Yi (-1000 ≤ Xi, Yi ≤ 1000) are the coordinates of the building, and Bi (1 ≤ Bi ≤ 1000) is the number of workers in this building.
The description of municipal buildings is followed by M lines that describe fallout shelters. Each line contains three integer numbers Pj, Qj, and Cj separated by spaces, where Pi, Qi (-1000 ≤ Pj, Qj ≤ 1000) are the coordinates of the fallout shelter, and Cj (1 ≤ Cj ≤ 1000) is the capacity of this shelter.
The description of The City Council's evacuation plan follows on the next N lines. Each line represents an evacuation plan for a single building (in the order they are given in The City description). The evacuation plan of ith municipal building consists of M integer numbers Ei,j separated by spaces. Ei,j (0 ≤ Ei,j ≤ 1000) is a number of workers that shall evacuate from the ith municipal building to the jth fallout shelter.
The plan in the input file is guaranteed to be valid. Namely, it calls for an evacuation of the exact number of workers that are actually working in any given municipal building according to The City description and does not exceed the capacity of any given fallout shelter.

Output

If The City Council's plan is optimal, then write to the output the single word OPTIMAL. Otherwise, write the word SUBOPTIMAL on the first line, followed by N lines that describe your plan in the same format as in the input file. Your plan need not be optimal itself, but must be valid and better than The City Council's one.

Sample Input

3 4
-3 3 5
-2 -2 6
2 2 5
-1 1 3
1 1 4
-2 -2 7
0 -1 3
3 1 1 0
0 0 6 0
0 3 0 2

Sample Output

SUBOPTIMAL
3 0 1 1
0 0 6 0
0 4 0 1

题解

这道题其实只是用了费用流里的一个定理，而和费用流这个算法本身没有太大的关系
我们考虑如果有一个负圈的话，那么必然，我们的水流在这个负圈上流一遍，就会减少我们的费用，可以管这个东西叫消圈定理
所以说，我们需要在残余网络里寻找一个负圈
残余网络怎么建？我们需要研究给出的这个网络来建图
由于我们只要找个更优解，所以大可不必考虑容量（能流一单位就行）
原点到每个大楼的边必然都流满了
残余网络里也是每个大楼流到原点，原点也不能走到别的地方，这些边对我们答案是没有用的，所以不加考虑
每条大楼走到每个救护站必然是一条容量为正无穷的边（如果认为它是容量为大楼工人个数的话也能做，处理起来会多几行代码，这每考虑的话比较方便），所以这里容量有剩余，连一条大楼到救护站的边，费用为距离
如果i大楼到j救护站有人过去的话，残余网络里一定有一条反边，add(j+n,i,-p)
如果j救护站有人，那么汇点到j救护站有反向边，add(n+m+1,j+n,0)
如果j救护站里还有空位，那么j到汇点连边 add(j+n,n+m+1,0)
我们终止的那个点不一定在负圈里，我们还要找到那个负圈
然后针对负圈里的每条边，如果它是大楼走到救护站的，就++ans[i][j]
如果它是救护站走到大楼的，就--ans[i][j]

代码

  1. #include <iostream>
  2. #include <algorithm>
  3. #include <cstring>
  4. #include <cstdio>
  5. #include <vector>
  6. #include <stack>
  7. #include <cmath>
  8. #define siji(i,x,y) for(int i=(x);i<=(y);++i)
  9. #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
  10. #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
  11. #define MOD 974711
  12. #define esp 1e-8
  13. //#define ivorysi
  14. using namespace std;
  15. typedef long long ll;
  17. int n,m;
  18. struct node {
  19.     int to,next,val;
  20. }edge[1000005];
  21. int head[2005],sumedge;
  22. void add(int u,int v,int c) {
  23.     edge[++sumedge].to=v;
  24.     edge[sumedge].next=head[u];
  25.     edge[sumedge].val=c;
  26.     head[u]=sumedge;
  27. }
  28. int x[1005],y[1005],b[1005];
  29. int p[1005],q[1005],c[1005];
  30. int ans[1005][1005];
  31. int st=-1;
  32. int dist[2005],pre[2005];
  33. bool vis[2005];
  34. int dis(int l,int z) {
  35.     return abs(x[l]-p[z])+abs(y[l]-q[z])+1;
  36. }
  37. bool spfa_dfs(int u) {
  38.     vis[u]=1;
  39.     for(int i=head[u];i;i=edge[i].next) {
  40.     int v=edge[i].to,w=edge[i].val;
  41.     if(dist[v]-w>dist[u]) {
  42.         dist[v]=dist[u]+w;
  43.         pre[v]=u;
  44.         if(!vis[v]) {if(spfa_dfs(v)) return true;}
  45.         else {
  46.         st=v;
  47.         return true;
  48.         }
  49.     }
  50.     }
  51.     vis[u]=0;
  52.     return false;
  53. }
  54. void solve() {
  55.     scanf("%d%d",&n,&m);
  56.     siji(i,1,n) {
  57.     scanf("%d%d%d",&x[i],&y[i],&b[i]);
  58.     }
  59.     siji(i,1,m) {
  60.     scanf("%d%d%d",&p[i],&q[i],&c[i]);
  61.     }
  62.     siji(i,1,n) {
  63.     siji(j,1,m) {
  64.         scanf("%d",&ans[i][j]);
  65.         add(i,j+n,dis(i,j));
  66.     }
  67.     }
  68.     siji(j,1,m) {
  69.     int flow=0;
  70.     siji(i,1,n) {
  71.         flow+=ans[i][j];
  72.         if(ans[i][j]!=0) {
  73.         add(j+n,i,-dis(i,j));
  74.         }
  75.     }
  76.     if(flow!=0) {
  77.         add(n+m+1,j+n,0);
  78.     }
  79.     if(flow!=c[j]) {
  80.         add(j+n,n+m+1,0);
  81.     }
  82.     }
  83.     siji(i,1,n+m) dist[i]=0x7f7f7f7f;
  84.     if(!spfa_dfs(n+m+1)) {
  85.     puts("OPTIMAL");
  86.     }
  87.     else {
  88.     puts("SUBOPTIMAL");
  89.     memset(vis,0,sizeof(vis));
  90.     while(!vis[pre[st]]) {
  91.         vis[pre[st]]=1;
  92.         st=pre[st];
  93.     }
  94.     int now=st;
  95.     do {
  96.         if(pre[now]<=n) {
  97.         ++ans[pre[now]][now-n];
  98.         }
  99.         else {
  100.         --ans[now][pre[now]-n];
  101.         }
  102.         now=pre[now];
  103.     }while(st!=now);
  104.     siji(i,1,n) {
  105.         siji(j,1,m) {
  106.         printf("%d%c",ans[i][j]," \n"[j==m]);
  107.         }
  108.     }
  109.     }
  110. }
  111. int main() {
  112. #ifdef ivorysi
  113.     freopen("f1.in","r",stdin);
  114. #endif
  115.     solve();
  117.     return 0;
  119. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注