首页 > 代码库 > POJ 1149

POJ 1149

2024-08-04 00:01:15   217人阅读

题目大意：

提前知道客户一个个前来的顺序以及手上的钥匙和对应的猪圈的猪的数量，合理安排猪圈放置猪的情况，达到最大售猪量

 

关键在于如何构造一个容量网络:

1.将顾客看做除源点和汇点以外的结点，并且另设两个结点；源点和终点

2.源点和每个猪圈的第一个顾客连边，边的权是开始时猪圈中猪的数量

3.若源点和某个结点之间有重边，则将权合并

4.顾客j紧跟在顾客i之后打开某个猪圈，因为猪圈可以存放的猪的数目可以是无穷的，那么就会有一条i->j,容量为+无穷的边

5.每个顾客和汇点之间都有一条权值为顾客需要猪的数量的边

 

这里用标点法解决，不断bfs标记点，回溯更新剩余网络，直到无法更新汇点.

  1 #include <cstdio>  2 #include <iostream>  3 #include <cstring>  4 #include <queue>  5 using namespace std;  6 #define N 105  7 #define M 1005  8 const int INF = 200000000;  9 int m,n,pigs[M],st,la,max_pig; 10 int vis[M]; 11 int pre[N] , minFlow[N]; //记录流过程用来回溯 , 到达i点的最小流量 12 struct Edge{ 13     int c , flow;//i，j之间的容量，流量 14 }; 15 Edge e[N][N]; 16  17 void build_graph() 18 { 19     int t , a , b; 20     memset(vis,0,sizeof(vis)); 21     for(int i = 1 ; i<=n ; i++){ 22         scanf("%d" , &t); 23         for(int j = 0 ; j<t ; j++){ 24             scanf("%d",&a); 25             if(!vis[a]){ 26                 e[st][i].c += pigs[a]; 27                 vis[a] = i; 28             } 29             else{ 30                 e[vis[a]][i].c = INF; 31                 vis[a] = i; 32             } 33         } 34         scanf("%d" , &b); //对应客人要买的猪的数量 35         e[i][la].c = b; 36     } 37 } 38  39 void ford() 40 { 41     //初始图流量为0  42     for(int i=st ; i<=la ; i++) 43             for(int j=st ; j<=la ; j++) 44                 e[i][j].flow = 0; 45     while(1){ 46         queue<int> q; 47         for(int i=st ; i<=la ; i++) pre[i] = -2; 48         q.push(st); 49         pre[st] = -1; 50  51         minFlow[st] = INF; 52         while(!q.empty() && pre[la] == -2){ 53             int u = q.front(); 54             q.pop(); 55             for(int i = 1 ; i<=la ; i++){ 56                 int tmp = e[u][i].c - e[u][i].flow; 57                 if(tmp > 0 && pre[i] < -1){ 58                     minFlow[i] = min(tmp , minFlow[u]); 59                     pre[i] = u; 60                     q.push(i); 61                 } 62             } 63         } 64  65  66         if(pre[la] < -1) break; 67  68         //更新剩余网络 69         for(int i  = pre[la] , u=la ; i!=-1 ; u=i , i=pre[i]){ 70             e[i][u].flow += minFlow[la]; 71             e[u][i].flow = -e[i][u].flow; 72         } 73     } 74     for(int i = 1; i<=n ; i++) 75     { 76         max_pig += e[i][la].flow; 77     } 78 } 79  80 int main() 81 { 82    // freopen("a.in" , "rb" , stdin); 83     while(~scanf("%d%d",&m,&n)){ 84         for(int i=1 ; i<=m ; i++) 85             scanf("%d",&pigs[i]); 86  87         st = 0 , la = n+1; 88         for(int i=st ; i<=la ; i++) 89             for(int j=st ; j<=la ; j++) 90                 e[i][j].c = 0; 91  92         max_pig = 0; 93  94         build_graph(); 95         ford(); 96  97         printf("%d" , max_pig); 98     } 99     return 0;100 }

 

POJ 1149


联系
我们