首页 > ACM题库 > HDU-杭电 > HDU 3917-Road constructions-图-[解题报告]HOJ
2015
04-14

HDU 3917-Road constructions-图-[解题报告]HOJ

Road constructions

问题描述 :

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?

输入:

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

输出:

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

样例输入:

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

样例输出:

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.

题目:http://acm.hdu.edu.cn/showproblem.php?pid=3917

题意:

            给出n,个工程,m个公司,给出每个公司施工需要上交的税务  tax,给出k 个 工程之间的关系,以及政府补助c,项目可处理对象 d!并且要求如果 选取i 公司担任这个工程,那么i 公司负责的项目也相应必须有它负责!!同时,与其” 相连 “的公司j 也必须担任” 相连“的任务!!!问政府可以获得的最高利润?!

解法:

      最大流最小割!

     最大利润=获得最大利益-支付最少补助!!!获得最大利益=雇佣公司税务之和! 支付最少补助=雇佣的公司的补助! 最大利润=所有公司税务之和-(未雇佣公司税务之和+支付最少补助)!!很显然,后面的为割,而为使利润最大割应最小!!ans=sum-max_flow!!

构图:

        我们首先 让 起始点 s 与各个 i 公司建边 边权为 tax[i],然后再让 各个公司i  与 sink 建边 ,权值为 担任的任务补助之和;并且 如果公司 i 和 j 存在“相连”关系的也建立边的关系,权值为inf;

代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<memory.h>
using namespace std;
const int M=10002;
const int INF=(1e9)-1;
int t,n,m,tot;
int gap[M],dis[M],pre[M],head[M],cur[M],s[M];
int NE,NV,sink,a[M],b[M],c[M],d[M];
struct Node
{
    int c,pos,next;
} E[M*4];
#define FF(i,NV) for(int i=0;i<NV;i++)
int sap(int s,int t)
{
    memset(dis,0,sizeof(int)*(NV+1));
    memset(gap,0,sizeof(int)*(NV+1));
    FF(i,NV) cur[i] = head[i];
    int u = pre[s] = s,maxflow = 0,aug =INF;
    gap[0] = NV;
    while(dis[s] < NV)
    {
loop:
        for(int &i = cur[u]; i != -1; i = E[i].next)
        {
            int v = E[i].pos;
            if(E[i].c && dis[u] == dis[v] + 1)
            {
                aug=min(aug,E[i].c);
                pre[v] = u;
                u = v;
                if(v == t)
                {
                    maxflow += aug;
                    for(u = pre[u]; v != s; v = u,u = pre[u])
                    {
                        E[cur[u]].c -= aug;
                        E[cur[u]^1].c += aug;
                    }
                    aug =INF;
                }
                goto loop;
            }
        }
        if( (--gap[dis[u]]) == 0)   break;
        int mindis = NV;
        for(int i = head[u]; i != -1 ; i = E[i].next)
        {
            int v = E[i].pos;
            if(E[i].c && mindis > dis[v])
            {
                cur[u] = i;
                mindis = dis[v];
            }
        }
        gap[ dis[u] = mindis+1 ] ++;
        u = pre[u];
    }
    return maxflow;
}
void addEdge(int u,int v,int c )
{
    E[NE].c = c;
    E[NE].pos = v;
    E[NE].next = head[u];
    head[u] = NE++;
    E[NE].c = 0;
    E[NE].pos = u;
    E[NE].next = head[v];
    head[v] = NE++;
}
int main()
{
    int n, m,sum, source, sink, vn,k;
    while(scanf("%d %d", &n, &m),(n||m))
    {
        NE=0,tot=0;
        sum = 0;
        source = 0;
        sink=m+1;
        NV=sink+1;
        memset(head, -1, sizeof(head));
        memset(s,0,sizeof(s));
        for(int i=1;i<=m;i++)
        {
            scanf("%d",&vn);
            addEdge(source,i,vn);
            sum+=vn;
        }
        scanf("%d",&k);
        for(int i=1;i<=k;i++)
        {
            scanf("%d%d%d%d",&a[i],&b[i],&d[i],&c[i]);
            s[d[i]]+=c[i];
        }
        for(int i=1;i<=k;i++)
        {
            for(int j=1;j<=k;j++)
            {
                if(i!=j&&b[i]==a[j]&&d[i]!=d[j])
                {
                    addEdge(d[i],d[j],INF);

                }
            }
        }
        for(int i=1;i<=m;i++)
        {
            addEdge(i,sink,s[i]);
        }
        printf("%d\n",sum-sap(source,sink));
    }
    return 0;
}

     

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/azheng51714/article/details/7866252


  1. 博主您好,这是一个内容十分优秀的博客,而且界面也非常漂亮。但是为什么博客的响应速度这么慢,虽然博客的主机在国外,但是我开启VPN还是经常响应很久,再者打开某些页面经常会出现数据库连接出错的提示

  2. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.