HDU 3917 Road constructions【最大权闭合子图 脑抽的建图】

Road constructions

Time Limit: 6000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 149    Accepted Submission(s): 46


Problem Description
N cities are required to connect with each other by a new transportation system. After several rounds of bidding, we have selected M constructions companies and 
decided which section is assigned to which company, the associated cost and the direction of each road. 

Due to the insufficiency of national fiscal revenue and special taxation system (the tax paid by each company pays is a fixed amount and tax payment occurs at the
beginning of the construction of the project)   The government wishes to complete the project in several years and collects as much tax as possible to support the public
expense

For the restrictions of construction and engineering techniques, if a company is required to start the construction, then itself and its associated companies have to 
complete all the tasks they commit (if company A constructs a road 
from city 1 to city 2, company B constructs a road from city 2 to city 3, company C constructs a road from city 1 to city 3, we call 
companies A and B are associated and other company pairs have no such relationship, pay attention, in this example and a are not associated, in other words,’ 
associated' is a directed relationship).   
Now the question is what the maximum income the government can obtain in the first year is?
 

Input
There are multiple cases (no more than 50).
  Each test case starts with a line, which contains 2 positive integers, n and m (1<=n<=1000, 1<=m<=5000).
  The next line contains m integer which means the tax of each company.
  The Third line has an integer k (1<=k<=3000)which indicates the number of the roads.
  Then k lines fellow, each contains 4 integers, the start of the roads, the end of the road, the company is responsible for this road and the cost of the road.
  The end of the input with two zero
 

Output
For each test case output the maximum income in a separate line, and if you can not get any income, please output 0.
 

Sample Input
4 2
500 10
4
1 2 1 10
2 3 1 20
4 3 1 30
1 4 2 60
4 2
500 100
5
1 2 1 10
2 3 1 20
4 3 1 30
4 3 2 10
1 4 2 60
3 1
10
3
1 2 1 100
2 3 1 100
3 1 1 100
0 0
 

Sample Output
440
470
0
Hint
for second test case, if you choose company 2 responsible ways, then you must choose the path of responsible company 1, but if you choose company 1, then you do not have to choose company 2.
 

Source

关于最大权闭合子图的最大流解法证明请参见胡伯涛Amber的集训队论文或者Ahuja的网络流算法书。还有NOI2006的最大获利。
这题建图就是,源点连每个公司,容量为收益(税收),汇点连每个公司,容量为总费用(每个公司所commit的),存在关系的公司之间连边,容量正无穷。
最后答案即为收益总和-最大流。
注意点:
1.我之前写最大获利的时候是建了4层的一个图,源-->收益点-->花费点-->汇。是因为每个收益点依赖的花费点有重叠的情况,重叠的不能重复算,所以必须靠流来自主选择;而本题只需3层即可,源-->收益点-->汇,因为每个收益点所必需的花费已然确定,直接把花费连到汇即可。
2.本题能用的到的点就3000个(k <= 3000)。。。我了个去。
3.建立公司之间的依赖关系太蛋疼了,为了这个重写了这代码三遍。第一次DFS,有标记会导致建立不全,无标记就是N!会TLE;第二次按城市点枚举建图,莫名其妙写错了,不知道错哪儿了;第三次按边枚举终于过了,期间还因为边开小了RE了一次,不过这道题的边数还真挺不好算的。。
总结:网络流永远是建图恶心,见过的模型越多越好。(最大权闭合子图-->点之间的依赖关系,有收益有花费)
代码:
#include <iostream>
#include 
<cstdio>
#include 
<cstring>
using namespace std;
#define maxn 5005
#define maxm 100000
#define maxtn 1005
#define maxk 3005
struct edge
{
    
int p,next,val,anti;
    edge(){}
    edge(
int _p,int _n,int _v):p(_p),next(_n),val(_v){}
    edge(
int _p,int _n,int _v,int _a):p(_p),next(_n),val(_v),anti(_a){}
}v[maxn],e[maxm],arc[maxn],temp[maxtn],ed[maxk];
int path[maxn],flow[maxn],pre[maxn],cnt[maxn],d[maxn];
int tot,n,tn,tm,tk,sum;
int value[maxn],cost[maxn];
const int inf = ~0u >> 1;
void init()
{
    tot 
= 0;
    sum 
= 0;
    n 
= tm + 1;
    
for(int i = 1;i <= tn;i++)temp[i].next = -1;
    
for(int i = 0;i <= n;i++)v[i].next = -1;
    memset(d,
0,sizeof(d));
    memset(cnt,
0,sizeof(cnt));
    memset(value,
0,sizeof(value));
    memset(cost,
0,sizeof(cost));
    cnt[
0= n + 1;
}
void add(int p,int q,int val)
{
    e[tot] 
= edge(q,v[p].next,val,tot + 1);
    v[p].next 
= tot++;
    e[tot] 
= edge(p,v[q].next,0,tot - 1);
    v[q].next 
= tot++;
}
void daa(int p,int q,int val,int id)
{
    ed[id] 
= edge(q,0,val);
    e[tot] 
= edge(q,temp[p].next,val);
    temp[p].next 
= tot++;
}
int mflow()
{
    
int s = 0,t = n;
    
int total,i,k,loc,least,now;
    
bool flag;
    
for(int i = 0;i <= n;i++)arc[i].next = v[i].next;
    
for(total = 0,i = s,now = inf;d[s] < n + 1;)
    {
        flow[i] 
= now;
        
for(flag = false,k = arc[i].next;~k;k = e[k].next)
        {
            
if(e[k].val && d[i] == d[e[k].p] + 1)
            {
                now 
= min(now,e[k].val);
                pre[e[k].p] 
= i;
                path[e[k].p] 
= k;
                arc[i].next 
= k;
                i 
= e[k].p;
                
if(i == t)
                {
                    
for(total += now;i != s;i = pre[i])
                    {
                        e[path[i]].val 
-= now;
                        e[path[i] 
^ 1].val += now;
                    }
                    now 
= inf;
                }
                flag 
= true;
                
break;
            }
        }
        
if(!flag)
        {
            
for(least = n + 1,k = v[i].next;~k;k = e[k].next)
            {
                
if(e[k].val && d[e[k].p] < least)
                {
                    least 
= d[e[k].p];
                    loc 
= k;
                }
            }
            cnt[d[i]]
--;
            
if(cnt[d[i]] == 0)
                
break;
            arc[i].next 
= loc;
            d[i] 
= least + 1;
            cnt[d[i]]
++;
            
if(i != s)
            {
                i 
= pre[i];
                now 
= flow[i];
            }
        }
    }
    
return total;
}
int main()
{
    
while(scanf("%d %d",&tn,&tm) == 2 && (tn || tm))
    {
        init();
        
for(int i = 1;i <= tm;i++)
        {
            scanf(
"%d",&value[i]);
            sum 
+= value[i];
        }
        scanf(
"%d",&tk);
        
for(int i = 0;i < tk;i++)
        {
            
int a,b,c,d;
            scanf(
"%d %d %d %d",&a,&b,&c,&d);
            cost[c] 
+= d;
            daa(a,b,c,i);
        }
        
for(int i = 0;i < tk;i++)
        {
            
int p = ed[i].p,a = ed[i].val;
            
for(int k = temp[p].next;~k;k = e[k].next)
            {
                
int b = e[k].val;
                
if(a != b)
                    add(a,b,inf);
            }
        }
        
for(int i = 1;i <= tm;i++)
        {
            add(
0,i,value[i]);
            add(i,n,cost[i]);
        }
        
int ans = mflow();
        printf(
"%d\n",sum - ans);
    }
}

posted on 2011-08-05 11:09 BUPT-[aswmtjdsj] @ Penalty 阅读(496) 评论(0)  编辑 收藏 引用 所属分类: 网络流HDU Solution Report


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

常用链接

留言簿(1)

随笔分类(150)

随笔档案(71)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜