PIGS

题目链接：http://poj.org/problem id=1149

题目大意：

迈克有个养猪场，养猪场里有M个猪圈，每个猪圈都上了锁。迈克没有钥匙，而要买猪的顾客一个接一个来到养猪场，每个顾客有一些猪圈的钥匙，要买一定数量的猪。当每个顾客来时，将有钥匙的猪圈全部打开，从中挑出一些买走，然后迈克可以重新分配这些猪圈里面的猪。当顾客离开后，门又被锁上。问迈克最多可以卖多少猪。

解题思路：

网络流的题目难就难在建图，这道题目的建图是这样的：

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include
#include
   
     #include
    
      #include
     
       #include
      
        #include
       
         #include
        
          #include
         
           #include
          
            #include
           
             #include
            
              #include
             
               #include
              
                #define maxn 1000 #define maxm 10000 #define INF (1<<30) #define PI acos(-1.0) #define mem(a, b) memset(a, b, sizeof(a)) #define For(i, n) for (int i = 0; i < n; i++) typedef long long ll; using namespace std; int M, N, A, K, B; int pig[maxn + 10] = {0}; int has[maxn + 10] = {0}; struct node { int v, f, nxt; }e[maxm * 2 + 10]; int g[maxn] = {0}, cnt, st = 0, ed; void add(int u, int v, int c) { e[++cnt].v = v; e[cnt].f = c; e[cnt].nxt = g[u]; g[u] = cnt; e[++cnt].v = u; e[cnt].f = 0; e[cnt].nxt = g[v]; g[v] = cnt; } void init() { cnt = 1; ed = N + 1; for (int i = 1; i <= M; i++) scanf("%d", pig + i); for (int i = 1; i <= N; i++) { scanf("%d", &A); int sum = 0; while(A--) { scanf("%d", &K); if (!has[K]) sum += pig[K]; else add(has[K], i, INF); has[K] = i; } add(st, i, sum); scanf("%d", &B); add(i, ed, B); } } int dis[maxn + 10], vis[maxn + 10], q[maxn + 10]; void bfs() { mem(dis, 0); int font = 0, rear = 1; q[font] = st; vis[st] = 1; while(font < rear) { int u = q[font++]; for (int i = g[u]; i; i = e[i].nxt) if (e[i].f && !vis[e[i].v]) { vis[e[i].v] = 1; q[rear++] = e[i].v; dis[e[i].v] = dis[u] + 1; } } } int dfs(int u, int delta) { if (u == ed) return delta; else { int ret = 0; for (int i = g[u]; i && delta; i = e[i].nxt) if (e[i].f && dis[e[i].v] == dis[u] + 1) { int dd = dfs(e[i].v, min(delta, e[i].f)); e[i].f -= dd; e[i ^ 1].f += dd; delta -= dd; ret += dd; } return ret; } } int maxflow() { int ret = 0; while(1) { mem(vis, 0); bfs(); if (!vis[ed]) return ret; ret += dfs(st, INF); } } int main () { scanf("%d%d", &M, &N); init(); printf("%d\n", maxflow()); return 0; }

（1）将顾客看做是除了源点和汇点以外的结点，并且另外设两个结点：源点和汇点。（2）源点和每个猪圈的第1个顾客连边，边的权是开始时猪圈中猪的数量。（3）若源点和每个结点之间有重边，可以合并。（4）顾客j紧跟顾客i之后打开猪圈，则边的权是正无穷大，因为如果j紧跟i之后打开，迈克可以根据j的需求将其他猪圈调到该猪圈，这样顾客j就可以买到尽可能多的猪。（5）每个顾客和汇点之间连边，表示顾客希望买猪的数目。
这样题目就成了基础的网络最大流。

[POJ 1149] PIGS (网络流最大流）

PIGS

题目链接：http://poj.org/problem id=1149

题目大意：

解题思路：