Road constructions
Time Limit: 6000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 313 Accepted Submission(s): 113
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 2011 Multi-University Training Contest 8 - Host by HUST
Recommend lcy 隻比HDU3879多了一點：公司i是公司j的附屬，那麼i到j連邊，容量為無限大。
#include<cstdio>
#include<cstring>
#include<vector>
#define N 8005
#define M 1000005
#define inf 999999999
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n,m,s,t,num,adj[N],dis[N],q[N];
vector<int> st[1005],ed[1005];
struct edge
{
int v,w,pre;
}e[M];
void insert(int u,int v,int w)
{
e[num]=(edge){v,w,adj[u]};
adj[u]=num++;
e[num]=(edge){u,0,adj[v]};
adj[v]=num++;
}
int bfs()
{
int i,x,v,head=0,tail=0;
memset(dis,0,sizeof(dis));
dis[s]=1;
q[tail++]=s;
while(head<tail)
{
x=q[head++];
for(i=adj[x];~i;i=e[i].pre)
if(e[i].w&&!dis[v=e[i].v])
{
dis[v]=dis[x]+1;
if(v==t)
return 1;
q[tail++]=v;
}
}
return 0;
}
int dfs(int x,int limit)
{
if(x==t)
return limit;
int i,v,tmp,cost=0;
for(i=adj[x];~i&&cost<limit;i=e[i].pre)
if(e[i].w&&dis[x]==dis[v=e[i].v]-1)
{
tmp=dfs(v,min(limit-cost,e[i].w));
if(tmp)
{
e[i].w-=tmp;
e[i^1].w+=tmp;
cost+=tmp;
}
else
dis[v]=-1;
}
return cost;
}
int Dinic()
{
int ans=0;
while(bfs())
ans+=dfs(s,inf);
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
int i,j,k,u,v,c,w[5005]={0},sum=0;
num=0;
memset(adj,-1,sizeof(adj));
s=0;
t=1;
for(i=1;i<=n;i++)
{
st[i].clear();
ed[i].clear();
}
for(i=1;i<=m;i++)
{
scanf("%d",w+i);
sum+=w[i];
insert(i+1,t,w[i]);
}
scanf("%d",&k);
for(i=1;i<=k;i++)
{
scanf("%d%d%d%d",&u,&v,&c,&w[0]);
insert(s,i+m+1,w[0]);
insert(i+m+1,c+1,inf);
st[u].push_back(c);
ed[v].push_back(c);
}
for(i=1;i<=n;i++)
{
for(j=0;j<ed[i].size();j++)
{
for(k=0;k<st[i].size();k++)
{
//printf("%d %d %d\n",i,ed[i][j],st[i][k]);
insert(st[i][k]+1,ed[i][j]+1,inf);
}
}
}
printf("%d\n",sum-Dinic());
}
}
由于選擇了一個公司必須選擇它的所有項目，是以可以把項目和公司合并為一個點。這樣點和邊都會減少。
#include<cstdio>
#include<cstring>
#include<vector>
#define N 5005
#define M 50005
#define inf 999999999
#define min(a,b) ((a)<(b)?(a):(b))
using namespace std;
int n,m,s,t,num,adj[N],dis[N],q[N];
vector<int> st[1005],ed[1005];
struct edge
{
int v,w,pre;
}e[M];
void insert(int u,int v,int w)
{
e[num]=(edge){v,w,adj[u]};
adj[u]=num++;
e[num]=(edge){u,0,adj[v]};
adj[v]=num++;
}
int bfs()
{
int i,x,v,head=0,tail=0;
memset(dis,0,sizeof(dis));
dis[s]=1;
q[tail++]=s;
while(head<tail)
{
x=q[head++];
for(i=adj[x];~i;i=e[i].pre)
if(e[i].w&&!dis[v=e[i].v])
{
dis[v]=dis[x]+1;
if(v==t)
return 1;
q[tail++]=v;
}
}
return 0;
}
int dfs(int x,int limit)
{
if(x==t)
return limit;
int i,v,tmp,cost=0;
for(i=adj[x];~i&&cost<limit;i=e[i].pre)
if(e[i].w&&dis[x]==dis[v=e[i].v]-1)
{
tmp=dfs(v,min(limit-cost,e[i].w));
if(tmp)
{
e[i].w-=tmp;
e[i^1].w+=tmp;
cost+=tmp;
}
else
dis[v]=-1;
}
return cost;
}
int Dinic()
{
int ans=0;
while(bfs())
ans+=dfs(s,inf);
return ans;
}
int main()
{
while(scanf("%d%d",&n,&m),n+m)
{
int i,j,k,u,v,c,w[5005]={0},sum=0;
num=0;
memset(adj,-1,sizeof(adj));
s=0;
t=m+1;
for(i=1;i<=n;i++)
{
st[i].clear();
ed[i].clear();
}
for(i=1;i<=m;i++)
{
scanf("%d",w);
sum+=w[0];
insert(i,t,w[0]);
}
scanf("%d",&k);
for(i=1;i<=k;i++)
{
scanf("%d%d%d%d",&u,&v,&c,w);
w[c]+=w[0];
st[u].push_back(c);
ed[v].push_back(c);
}
for(i=1;i<=m;i++)
insert(s,i,w[i]);
for(i=1;i<=n;i++)
for(j=0;j<ed[i].size();j++)
for(k=0;k<st[i].size();k++)
if(st[i][k]!=ed[i][j])
insert(st[i][k],ed[i][j],inf);
printf("%d\n",sum-Dinic());
}
}
![DB2表壓縮功能[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)