【NEERC 2003】有向图破坏

【题目描述】

Alice和Bob正在玩如下的游戏。首先Alice画一个有N个顶点，M条边的有向图。然后Bob试着摧毁它。在一次操作中他可以找到图中的一个点，并且删除它所有的入边或所有的出边。

Alice给每个点定义了两个值：Wi+和Wi-。如果Bob删除了第i个点所有的入边他要给Alice付Wi+元，如果他删除了所有的出边就需要给Alice付Wi元。

找到Bob删除图中所有边需要的最小花费。

【输入格式】

输入数据描述了Alice画下的图。

输入文件的第一行有两个数N,M(1<=N<=100,1<=M<=5000)。第二行有N个整数，描述了N个点的Wi+，同样的第三行是这N个点的Wi-。所有的费用都是正数并且不超过10^6。接下来的M行每行有两个数，代表有向图中相应的一条边。

【输出格式】

输出一行一个整数，即Bob的最小花费。

【分析】

很容易想到，把每个点拆成两个点，一个控制出边，一个控制入边，保留原边后很明显的一个最小权点覆盖集，Dinic就行了。

 1 #include <cstdlib>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdio>
 5 #include <queue>
 6 const int maxn=500;
 7 const int INF=10000*10000;
 8 using namespace std;
 9 struct tu
10 {
11        int c,f;
12        tu(){c=0;f=0;}
13 }maps[maxn][maxn];
14 int dist[maxn],n,m;
15 
16 void Dinic();
17 bool BFS();//构建层次网络 
18 int dfs(int v,int low);
19 
20 int main()
21 {
22     int i;
23     //文件操作
24     freopen("destroyingthegraph.in","r",stdin);
25     freopen("destroyingthegraph.out","w",stdout);
26     memset(maps,0,sizeof(maps));
27     
28     scanf("%d%d",&n,&m);//n个点,m条边 
29     
30     for (i=1;i<=n;i++) scanf("%d",&maps[i+n][2*n+1].c);//w+
31     for (i=1;i<=n;i++) scanf("%d",&maps[0][i].c);//w-
32     
33     for (i=1;i<=m;i++) 
34     {
35         int u,v;
36         scanf("%d%d",&u,&v);
37         maps[u][v+n].c=INF;
38     }
39     Dinic();
40     return 0;
41 }
42 void Dinic()
43 {
44      int flow=0;
45      while ( BFS() )
46      {
47            int temp=0;
48            if (temp=dfs(0,INF)) flow+=temp;
49      }
50      printf("%d
",flow);
51 }
52 bool BFS()//层次网络
53 {
54      queue<int>Q;
55      int i;
56      memset(dist,-1,sizeof(dist));
57      dist[0]=0;
58      Q.push(0);
59      while (!Q.empty())
60      {
61            int u=Q.front();Q.pop();
62            for (i=0;i<=(2*n+1);i++)
63            {
64                int v=i;
65                if(maps[u][v].c-maps[u][v].f>0 && dist[v]==-1)
66                {
67                   dist[v]=dist[u]+1;
68                   Q.push(v);
69                } 
70            } 
71      }
72      return (dist[(2*n)+1]!=-1);
73 } 
74 int dfs(int u,int low)
75 {
76      if (u==(2*n)+1 || low==0) return low;
77      int flow=0,f,i;
78      for (i=0;i<=(2*n)+1;i++)
79      {
80          int v=i;
81          if (maps[u][v].c>maps[u][v].f && dist[v]==dist[u]+1)
82          {
83              if (f=dfs(i,min(low,maps[u][v].c-maps[u][v].f)))
84              {
85                  maps[u][v].f+=f;
86                  maps[v][u].f-=f;
87                  low-=f;
88                  flow+=f;
89                  if (low==0) break;
90              }
91          }
92      }
93      return flow;
94 }

View Code