加载中…HDU 3917 Road constructions 最大权闭合图 2011 Multi-University Training Contest 8 - Host by HUST
(2011-08-05 09:02:01)
标签：
hdu3917roadconstructions最大权闭合图it |
分类： 网络流 |
题目描述：
给你n个城市，m个公司，若干条可能要建设的道路，每条有向道路需要花费，还有负责建设这条道路的公司编号，如果要建设ab道路，那么负责这条道路的公司需要建设完它负责的所有道路，而且对负责道路bx（x任意）的公司同样要求，以此类推。
每个公司还要交税，问最多能收多少税。
解题报告：
最大权闭合图，val[i]表示第i个公司的交税额减去它负责所有道路的花费，即，政府选择这个公司的纯收益是多少。
然后，对于第i号公司，遍历它负责的边a,b,再看所有负责以b为起点的公司j，表示如果选了i公司，就一定要选j公司。
有了上述信息，已经完全转化成最大权闭合图（hbt的论文），建图如下：原点s链接所有val为正的公司，容量为val，所有val为负的公司链接汇点t，容量为-val。如果选了i就必须选j，链接ij，容量无穷。
所有，所有正点权和减去最大流就是答案。
代码如下：
e[cnt].from = from, e[cnt].to = to; e[cnt].val =
va;
e[cnt].next = v[from];v[from] = cnt++;
e[cnt].from = to, e[cnt].to = from; e[cnt].val =
0;
e[cnt].next = v[to];v[to] = cnt++;
int
head, tail, id;
head =
tail = 0; que[tail++] = s;
memset(dis, -1, sizeof(int) * n);dis[s] =
0;
while(head != tail) //
bfs,得到顶点i的距s的最短距离dis[i]
for(id = v[que[head++]]; id !=
-1; id = e[id].next)
if (e[id].val > 0
&& dis[e[id].to] == -1)
{
dis[e[id].to] = dis[e[id].from] + 1;
que[tail++]
= e[id].to;
if
(e[id].to == t) return true;
}
return
false;
int
maxflow = 0, tmp, i;
while(bfs(n, s, t))
{
int u = s, tail = 0;
for(i = 0; i <
n; i++) cur[i] = v[i];
while(cur[s] != -1)
if (u != t &&
cur[u] != -1 && e[cur[u]].val
> 0 && dis[u] != -1
&& dis[u] + 1 ==
dis[e[cur[u]].to])
{que[tail++] = cur[u]; u = e[cur[u]].to;}
else if (u == t)
{
for(tmp =
Max, i = tail - 1; i >= 0; i--) tmp = min(tmp,
e[que[i]].val);
for(maxflow
+= tmp, i = tail - 1; i >= 0; i--)
{
e[que[i]].val -= tmp;
e[que[i] ^ 1].val +=
tmp;
if (e[que[i]].val == 0) tail =
i;
}
u =
e[que[tail]].from;
}
else
{
while(tail
> 0 && u != s
&& cur[u] == -1) u =
e[que[--tail]].from;
cur[u] =
e[cur[u]].next;
}
}
return
maxflow;
while(scanf("%d%d", &n,
&m) && (n ||
m))
{
for(int i = 1; i
<= m; i++) scanf("%d",
&val[i]);
for(int i = 1; i
<= m; i++) com[i].clear();
for(int i = 1; i
<= n; i++) have[i].clear();
int t;scanf("%d",
&t);
while(t--)
{
int a, b, c, d;scanf("%d%d%d%d",
&a, &b, &c,
&d);
val[c] -= d;
have[a].push_back(c);
com[c].push_back(b);
}
memset(v, -1, sizeof(v)); cnt
= 0;
int ss = 0, tt = m + 1, ans =
0;
for(int i = 1; i
<= m; i++)
{
if (val[i] > 0) ans += val[i],
insert(ss, i, val[i]);
if (val[i] < 0) insert(i, tt,
-val[i]);
}
for(int i = 1; i
<= m; i++)
{
memset(vst, 0, sizeof(vst)); vst[i] = 1;
for(int j = 0; j < com[i].size();
j++)
{
int id =
com[i][j];
for(int k =
0; k < have[id].size(); k++)
{
int to = have[id][k];
if (!vst[to])
{
vst[to] = 1;
insert(i, to, Max);
//cout << i
<< ' '
<< to
<< endl;
}
}
}
}
ans = ans - Dinic(tt + 1, ss,
tt);
if (ans <= 0)
printf("0\n");
else printf("%d\n",
ans);
}
return
0;
给你n个城市，m个公司，若干条可能要建设的道路，每条有向道路需要花费，还有负责建设这条道路的公司编号，如果要建设ab道路，那么负责这条道路的公司需要建设完它负责的所有道路，而且对负责道路bx（x任意）的公司同样要求，以此类推。
每个公司还要交税，问最多能收多少税。
解题报告：
最大权闭合图，val[i]表示第i个公司的交税额减去它负责所有道路的花费，即，政府选择这个公司的纯收益是多少。
然后，对于第i号公司，遍历它负责的边a,b,再看所有负责以b为起点的公司j，表示如果选了i公司，就一定要选j公司。
有了上述信息，已经完全转化成最大权闭合图（hbt的论文），建图如下：原点s链接所有val为正的公司，容量为val，所有val为负的公司链接汇点t，容量为-val。如果选了i就必须选j，链接ij，容量无穷。
所有，所有正点权和减去最大流就是答案。
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
#define Max 0x1fffffff
#define SIZE 6000
struct edge{int from, to, val, next;}e[14000000];
int v[SIZE], que[SIZE * 10], dis[SIZE], cnt, cur[SIZE];
void insert(int from, int to, int va)
{
}
bool bfs(int n, int s, int t)
{
}
int Dinic(int n, int s, int t)
{
}
vector<int> have[2000],
com[SIZE];
int val[6000], vst[SIZE];
int n, m;
int main()
{
}
喜欢
0
赠金笔