Base Station
Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 65768/32768 K (Java/Others)
Total Submission(s): 844 Accepted Submission(s): 353
Problem Description
A famous mobile communication company is planning to build a new set of base stations. According to the previous investigation, n places are chosen as the possible new locations to build those new stations. However, the condition of each position varies much, so the costs to built a station at different places are different. The cost to build a new station at the ith place is Pi (1<=i<=n).
When complete building, two places which both have stations can communicate with each other.
Besides, according to the marketing department, the company has received m requirements. The ith requirement is represented by three integers Ai, Bi and Ci, which means if place Ai and Bi can communicate with each other, the company will get Ci profit.
Now, the company wants to maximize the profits, so maybe just part of the possible locations will be chosen to build new stations. The boss wants to know the maximum profits.
Input
Multiple test cases (no more than 20), for each test case:
The first line has two integers n (0<n<=5000) and m (0<m<=50000).
The second line has n integers, P1 through Pn, describes the cost of each location.
Next m line, each line contains three integers, Ai, Bi and Ci, describes the ith requirement.
Output
One integer each case, the maximum profit of the company.
Sample Input
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
Sample Output
Author
liulibo
Source
Recommend
lcy
论文题，Amber最小割模型里面的，最大权闭合图，因为数组开的太大了，吃了一次RE......
最大权闭合图不用说了，边看成收益点，连向S，流量是点权，站点看成花费点，连向T，流量也是点权，其他按照原图连边，流量是无限大，之后做一次最小割，割值就是你未选的收益点+选定花费点（因为是闭合图，所以割肯定是简单割，想一下割的定义，就明白割值的含义了），用你总收益-割值，就是答案。
用SAP求的最小割，渐渐爱上SAP了，Dinic不用了.....
代码：
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
const int maxnode = 60000;
const int maxedge = 320000;
const long long inf = (1LL << 35);
int S, T, cnt;
int head[maxnode], gap[maxnode], pre[maxnode], cur[maxnode], dis[maxnode];
struct Edge
{
int s, t;
int next;
long long w;
} st[maxedge];
void init()
{
memset(head, -1, sizeof(head));
cnt = 0;
}
void AddEdge(int s, int t, long long w)
{
st[cnt].s = s;
st[cnt].t = t;
st[cnt].w = w;
st[cnt].next = head[s];
head[s] = cnt;
cnt++;
st[cnt].s = t;
st[cnt].t = s;
st[cnt].w = 0;
st[cnt].next = head[t];
head[t] = cnt;
cnt++;
}
void bfs()
{
memset(gap, 0, sizeof(gap));
memset(dis, -1, sizeof(dis));
queue <int> Q;
Q.push(T);
dis[T] = 0;
gap[0] = 1;
int k, t;
while (!Q.empty())
{
k = Q.front();
Q.pop();
for (int i = head[k]; i != -1; i =st[i].next)
{
t = st[i].t;
if (dis[t] == -1 && st[i ^ 1].w > 0)
{
dis[t] = dis[k] + 1;
gap[dis[t]]++;
Q.push(t);
}
}
}
}
long long sap()
{
int i;
for (i = S; i <= T; ++i)
cur[i] = head[i];
pre[S] = S;
int u = S, v;
long long flow = 0;
long long aug = inf;
bool flag;
while (dis[S] <= T)
{
flag = false;
for (i = cur[u]; i != -1; i = st[i].next)
{
v = st[i].t;
if (st[i].w > 0 && dis[u] == dis[v] + 1)
{
cur[u] = i;
flag = true;
pre[v] = u;
aug = (aug > st[i].w) ? st[i].w : aug;
u = v;
if (v == T)
{
flow += aug;
for (u = pre[u]; v != S; u = pre[u])
{
v = u;
st[cur[u]].w -= aug;
st[cur[u] ^ 1].w += aug;
}
aug = inf;
}
break;
}
}
if (flag == true) continue;
int mint = T;
for (i = head[u]; i != -1; i = st[i].next)
{
v = st[i].t;
if (st[i].w > 0 && mint > dis[v])
{
cur[u] = i;
mint = dis[v];
}
}
gap[dis[u]]--;
if (gap[dis[u]] == 0) break;
gap[dis[u] = mint + 1]++;
u = pre[u];
if (u == S) aug = inf;
}
return flow;
}
int main()
{
int n, m;
while (scanf("%d%d", &n, &m) != EOF)
{
init();
S = 0;
T = n + m + 1;
int sum = 0;
for (int i = 1; i <= n; ++i)
{
int x;
scanf("%d", &x);
AddEdge(m + i, T, x);
}
for (int i = 1; i <= m; ++i)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
AddEdge(S, i, c);
AddEdge(i, m + a, inf);
AddEdge(i, m + b, inf);
sum += c;
}
bfs();
sum -= sap();
printf("%d\n", sum);
}
return 0;
}
posted on 2011-10-15 22:10
LLawliet 阅读(110)
评论(0) 编辑 收藏 引用 所属分类:
网络流