zoj 3135 Party of 8g 最大点权独立集

题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3165

题意：有M个男孩和N个女孩他们每个人都有一个love值。

现在要邀请他们中的一部分人，满足他们之间没有“8g”关系。

给出M,N,S. S表示有S对boy和girl之间有“8g”关系。

思路：

最大点权独立集。

原图基础上增加源s和汇t。

s向每个boy连一条边,容量为这个人的love值。

每个girl向t连一条边,容量为这个人的love值。

然后每对"bg"关系boy向girl连一条边，容量为正无穷。

求最小割。答案 = 权值总和 - 最小割

再输出哪几个男孩和女孩被邀请了。

  1 #include <bits/stdc++.h>
  2 using namespace std;
  3 #define maxn 205
  4 const int inf = 0x3f3f3f3f;
  5 struct Edge
  6 {
  7     int from, to, cap, flow;
  8     Edge(int f, int t, int c, int fl)
  9     {
 10         from = f; to = t; cap = c; flow = fl;
 11     }
 12 };
 13 vector <Edge> edges;
 14 vector <int> G[maxn];
 15 int vis[maxn], cur[maxn], d[maxn];
 16 int s, t, n, m;
 17 void AddEdge(int from, int to, int cap)
 18 {
 19     edges.push_back(Edge(from, to, cap, 0));
 20     edges.push_back(Edge(to, from, 0, 0));
 21     m = edges.size();
 22     G[from].push_back(m-2);
 23     G[to].push_back(m-1);
 24 }
 25 bool bfs()
 26 {
 27     memset(vis, 0, sizeof(vis));
 28     d[s] = 0; 
 29     vis[s] = 1;
 30     queue <int> q;
 31     q.push(s);
 32     while(!q.empty())
 33     {
 34         int u = q.front(); q.pop();
 35         for(int i = 0 ; i < G[u].size(); i++)
 36         {
 37             Edge &e = edges[G[u][i]];
 38             if(!vis[e.to] && e.cap > e.flow)
 39             {
 40                 d[e.to] = d[u]+1;
 41                 vis[e.to] = 1;
 42                 q.push(e.to);
 43             }
 44         }
 45     }
 46     return vis[t];
 47 }
 48 int dfs(int x, int a)
 49 {
 50     if(x == t || a == 0) return a;
 51     int flow = 0, f;
 52     for(int &i = cur[x]; i < G[x].size(); i++)
 53     {
 54         Edge &e = edges[G[x][i]];
 55         if(d[x] + 1 == d[e.to] && (f = dfs(e.to, min(a, e.cap - e.flow))) > 0)
 56         {
 57             e.flow += f;
 58             edges[G[x][i]^1].flow -= f;
 59             flow += f;
 60             a -= f;
 61             if(a == 0) break;
 62         }
 63     }
 64     return flow;
 65 }
 66 int Maxflow()
 67 {
 68     int flow = 0;
 69     while(bfs())
 70     {
 71         memset(cur, 0, sizeof(cur));
 72         flow += dfs(s, inf);
 73     }
 74     return flow;
 75 }
 76 int N, M, S;
 77 int b[110], g[110];
 78 int main()
 79 {
 80     while(~scanf("%d%d%d", &M, &N, &S))
 81     {
 82         edges.clear();
 83         for(int i = 0; i <= N+M+1; i++) G[i].clear();
 84         s = 0; t = N+M+1;
 85         int temp;
 86         int sum = 0;
 87         memset(b, 0, sizeof(b));
 88         memset(g, 0, sizeof(g));
 89         for(int i = 1; i <= M; i++) //BOY
 90         {
 91             scanf("%d", &temp);
 92             sum += temp;
 93             AddEdge(s, i, temp);
 94         }
 95         for(int i = 1; i <= N; i++) //GIRL
 96         {
 97             scanf("%d", &temp);
 98             sum += temp;
 99             AddEdge(i+M, t, temp);
100         }
101         for(int i = 1; i <= S; i++)
102         {
103             int a, b; scanf("%d%d", &a, &b);
104             AddEdge(a, b+M, inf);
105         }
106         int flow = Maxflow();
107         sum -= flow;
108         //cout<<sum<<endl;
109         int cntb = 0, cntg = 0;
110         for(int i = 0; i < m; i+=2)
111         {
112             if(edges[i].from == s)
113             {
114                 if(vis[edges[i].to])
115                 {
116                     b[edges[i].to] = 1;
117                     cntb++;
118                 }
119                     
120             }
121             if(edges[i].to == t)
122             {
123                 if(!vis[edges[i].from])
124                 {
125                     g[edges[i].from-M] = 1;
126                     cntg++;
127                 }
128             }
129         }
130         printf("%d %d %d
", sum, cntb, cntg);
131         bool flag = true;
132         for(int i = 1; i <= M; i++)
133         {
134             if(b[i])
135             {
136                 if(flag) printf("%d", i), flag = false;
137                 else printf(" %d",i);
138             }
139         }
140         printf("
");
141         flag = true;
142         for(int i = 1; i <= N; i++)
143         {
144             if(g[i])
145             {
146                 if(flag) printf("%d", i), flag = false;
147                 else printf(" %d", i);
148             }
149         }
150         printf("
");
151     }
152     return 0;
153 }