Oooooooo AAAAE

题面：

这个游戏可以简化成：谱面由N个键和M条连线组成，每两个键之间有一个连线，玩家需要在键之间滑动，且连线的方向是固定的，玩家每次选择一个键，把所有从这个键出发的连线都消除掉，花费为ai，也可以将每个结束在这个点的连线消除，花费Bi。不用担心，LiMn2O4的手指足够多。最后让连线全部消失，得分就是总花费。花费越少，分数越高。求出最小花费。

思路：

1.最小点权覆盖集：从x或者y集合中选取一些点，使这些点覆盖所有的边，并且选出来的点的权值尽可能小。最大点权独立集：在二分图中找到权值和最大的点集，使得它们之间两两没有边。
2.借鉴了题解的思路。才知道是网络流最小点权覆盖问题。设立源点s和t，s连边到点i，容量为i点的权值；点j连边到t，容量为j点权值；原二分图中的边容量为INF，求最大流即为最小点权覆盖。
3.扩展：最大点权独立集可转化为最小点权覆盖问题，

最大点权独立集 = 总权值 - 最小点权覆盖集

经典的网络流最小点权覆盖问题，首先拆点，分成左右两部分，源点向所有左节点连一条边，流量为删除出边的花费。所有右节点向汇点连一条边，流量为删除入边的费用。对于每条输入给定的边<u,v>，其在左边的点为u,v，右边的点为u’,v’，那么我们连一条<u,v’>的边，流量为∞（正无穷才不会对可行流上最小的容量产生限制）。跑一边最大流，得到的答案就是最小的费用。
首先，如果没有花费的话，这道题就是简单的最小点覆盖集。加上了点权之后，我们就要将最小割的思想融合进去。要注意费用，一定要符合S->T的顺序

代码：

  1 #include<bits/stdc++.h>
  2 const int inf = 0x3f3f3f3f;
  3 using namespace std;
  4  
  5 int n, m, t, h[250];
  6 int a[110], b[110];
  7 int d[250];
  8 queue<int>q;
  9  
 10 struct node
 11 {
 12     int t,n,w; 
 13 }E[20000];
 14  
 15 void add(int u, int v, int w)
 16 {
 17     E[t].t=v;
 18     E[t].w=w;
 19     E[t].n = h[u];
 20     h[u] =t++;
 21 }
 22  
 23 int bfs(int s, int t) 
 24 {
 25     if(s== t)
 26         return 0;
 27     while(q.size())
 28         q.pop();
 29     memset(d,-1,sizeof(d));
 30     d[s] = 1;
 31     q.push(s);
 32     while(q.size())
 33     {
 34         int k = q.front();
 35         q.pop();
 36         for(int i = h[k]; i != -1; i = E[i].n)
 37         {
 38             int to = E[i].t;
 39             if(d[to] == -1 && E[i].w > 0)
 40             {
 41                 d[to] = d[k] + 1;
 42                 q.push(to);
 43             }
 44         }
 45     }
 46     return d[t] != -1;
 47 }
 48 int dfs(int x, int t, int cnt)
 49 {
 50     if(x==t)
 51         return cnt;
 52     for(int i = h[x]; i != -1; i = E[i].n)
 53     {
 54         int to = E[i].t;
 55         if(d[to] == d[x] + 1 && E[i].w > 0)
 56         {
 57             int f = dfs(to, t, min(E[i].w, cnt));
 58             if(f> 0)
 59             {
 60                 E[i].w -= f;
 61                 E[i^1].w += f;
 62                 return f;
 63             }
 64         }
 65     }
 66     return -1;
 67 }
 68  
 69 void dinic(int s, int t)
 70 {
 71     long long ans = 0;
 72     while(bfs(s, t))
 73     {
 74         while(1)
 75         {
 76             int k= dfs(s, t, inf);
 77             if(k == -1)
 78                 break;
 79             ans += k;
 80         }
 81     }
 82     printf("%lld
", ans);
 83 }
 84  
 85 int main()
 86 {
 87     memset(h,-1,sizeof(h));
 88     scanf("%d%d", &n, &m); 
 89     for(int i = 1; i <= n; i ++) 
 90     {
 91         scanf("%d", &a[i]);
 92         add(i + n, 2 * n + 1, a[i]);
 93         add(2 * n + 1, i + n, 0);
 94     }
 95     for(int i = 1; i <= n; i ++)
 96     {
 97         scanf("%d", &b[i]);
 98         add(0, i, b[i]);
 99         add(i, 0, 0);
100     }
101     for(int i = 1; i <= m; i ++)
102     {
103         int a, b;
104         scanf("%d%d", &a, &b);
105         add(a, b + n, inf);
106         add(b + n, a, 0);
107     }
108     dinic(0, 2 * n + 1);
109 }

View Code