最大权闭合子图

By admin in 亚洲必赢app在哪下载 on 2019年2月15日

1497: [NOI2006]最大获利

Time Limit: 5 Sec  Memory
Limit: 64 MB
Submit: 5503  Solved: 2673

Description

新的技艺正碰上开始机通信市集,对于各小运转商来说,那既是机遇,更是挑衅。THU公司旗下的CS&T通信公司在新一代通信技术血战的前夕,须要做太多的准备工作,仅就站址拔取一项,就必要形成早先时代市镇切磋、站址勘测、最优化等档次。在最初市镇调研和站址勘测之后,集团取得了总共N个可以当作通信信号中转站的地点,而由于这个地址的地理地点距离,在差其他地点修建通信中转站要求投入的资本也是不等同的,所幸在先前时代调查之后这几个都以已知多少:建立第i个通信中转站需求的本金为Pi(1≤i≤N)。另民有公司业调查得出了全数希望中的用户群,一共M个。关于第i个用户群的音信包蕴为Ai,
Bi和Ci:这一个用户会动用中转站Ai和中转站Bi进行电视揭橥,集团可以收入Ci。(1≤i≤M,
1≤Ai, Bi≤N)
THU集团的CS&T公司可以有采用的树立部分中转站(投入开支),为局地用户提供劳务并收获收入(收益之和)。那么如何挑选最后创制的中转站才能让商户的净毛利最大啊?(净获利
= 受益之和 – 投入资金之和)

Input

输入文件中第2行有三个正整数N和M
。第壹,行中有N个整数描述每1个通信中转站的确立资金,依次为P1, P2, …, PN
。以下M行,第(i + 2)行的多少个数Ai,
Bi和Ci描述第i个用户群的信息。全体变量的含义可以瞻仰标题叙述。

Output

您的次第3旦向输出文件输出三个整数,表示公司可以得到的最大净纯利。

Sample Input

5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
亚洲必赢app在哪下载,1 4 2
4 5 3

Sample Output

4

HINT

 

【样例表明】选取创立一,贰,3号中转站,则需求投入花费6,获利为10,因而得到最大收益4。【评分方法】本题没有部分分,你的次第的出口唯有和大家的答案完全一致才能赢得满分,否则不得分。【数据规模和预订】
8/10的数目中:N≤200,M≤1 000。 百分百的数码中:N≤5 000,M≤陆仟0,0≤Ci≤100,0≤Pi≤100。

分析

一,求最大权闭合子图

推荐文章:胡伯涛
《最小割模型在新闻学竞技前的应用》

对此图闭合图建成网络,是:构造三个源点S,汇点T。将S与全体权值为正的点连一条体积为其权值的边,将T全部权值为负的点连一条体量为其权值的相对值的边,原来的边将其容积定为正无穷。

那就是说怎么利用到标题上吗,须要展开转载一下。

大家得以了然成:人是正权值的点(有收入),中转站是负权值的的点(建造须要资本),逐个人有两个所属的中转站,人和七个中转站之间有两条边。是否很奇特

如此那般就形成了一个闭合图,用位置的话,构造2个起源S,汇点T,正权值点(人)向S连边,容积就是点的权值;负权值点(中转站)向T连边,体量是点权值得相对;原来的边体积正无穷。

网络图就社团好了,就是下边的图,求出最小割,即最大流,用sum-最大流。sum全部人带来的收益的和(全体正权值点的权值和)

二,另一种了然形式,补充

对此那样建图,其实还足以这么精通的,我再补充一下,假如明白求最大权闭合图,就可以做了,可以直接跳过。

我们建好图后,就是上面的图,然后求最小割,为何求最小割呢(上边小说中有,那是另一种思路)。

求最小割其实就是求最少的费用,sum是全体人的带来的进项和,那么sum把拥有的进项加起来了,减去消费不就是最大收益吗?那就是干吗求最小割了。

记住:最小割是消费,要让费用尽量小。

那么求最小割了,设最小割是ans开支,随后要用sum-ans:

  • 先是中间的绿边是必定无法切的,切一条绿边的消费就是正无穷了!!!
  • 切红边是怎样意思呢:表示此人的入账不要了,不须求满意她了
  • 切蓝边:这么些中转站建(意会一下,ans+中转站的标价,然后sum再减去,都减去开销,当然建啊)

接下来可能有疑难了:会不会自小编切了红边(不要此人的收入了),又把属于他的练歌蓝边切了。

本来不容许,绿边可不是凑了闹的,比如对于点a1,他有两条边s-a1-b1-t,s-a1-b2-t,假使切了s-a1那两条边已经断开了,再切b1-t,b2-t没怎么用。

好了,到那了,突然发现打了如此多字,大概表述不知底,qwq

亚洲必赢app在哪下载 1

 

code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<queue>
 4 #include<cstring>
 5 
 6 using namespace std;
 7 
 8 const int MAXN = 100100;
 9 const int INF = 0x7fffffff;
10 struct Edge{
11     int to,nxt,c;
12 }e[500100];
13 int sum,tot = 1,n,m,s,t,ans;
14 int head[MAXN], val[MAXN],dis[MAXN];
15 queue<int>q;
16 
17 
18 int read()
19 {
20     int x = 0,f = 1;char ch = getchar();
21     for (; ch<'0'||ch>'9'; ch = getchar())
22         if (ch=='-') f = -1;
23     for (; ch>='0'&&ch<='9'; ch = getchar())
24         x = x*10+ch-'0';
25     return x*f;
26 }
27 void add_edge(int u,int v,int w)
28 {
29     ++tot;
30     e[tot].c = w,e[tot].to = v,e[tot].nxt = head[u];
31     head[u] = tot;
32     ++tot;
33     e[tot].c = 0,e[tot].to = u,e[tot].nxt = head[v];
34     head[v] = tot;
35 }
36 bool bfs()
37 {
38     memset(dis,-1,sizeof(dis));
39     q.push(s);
40     dis[s] = 0;
41     while (!q.empty())
42     {
43         int u = q.front();
44         q.pop();
45         for (int i=head[u]; i; i=e[i].nxt)
46         {
47             int v = e[i].to;
48             if (dis[v]==-1 && e[i].c>0)
49             {
50                 dis[v] = dis[u]+1;
51                 q.push(v);
52             }
53         }
54     }
55     if (dis[t]!=-1) return true;
56     return false;
57 }
58 int dfs(int u,int low)
59 {
60     if (u==t) return low;
61     int w ,tmp = low;
62     for (int i=head[u]; i; i=e[i].nxt)
63     {
64         int v = e[i].to;
65         if (dis[v]==dis[u]+1 && e[i].c> 0)
66         {
67             w = dfs(v,min(low,e[i].c));
68             e[i].c -= w;
69             e[i^1].c += w;
70             low -= w;
71         }
72     }
73     return tmp - low;
74 }
75 int main()
76 {
77     n = read();m = read();
78     s = 0,t = n+m+1;
79     for (int x,i=1; i<=n; ++i)
80     {
81         x = read();
82         add_edge(i+m,t,x);//建立从中转站到T的边,中转站的花费 
83     }
84     for (int x,y,z,i=1; i<=m; ++i)
85     {
86         x = read(),y = read(),z = read();
87         sum += z;
88         add_edge(i,m+x,INF);//建立第i个人到中转站的边INF 
89         add_edge(i,m+y,INF);
90         add_edge(s,i,z);//建立从S到第i个人的边,第i个人的获益 
91     }
92     while (bfs())
93         ans += dfs(s,INF);
94     printf("%d",sum-ans);
95     return 0;
96 }

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 亚洲必赢app官方下载 版权所有