BZOJ-1834 网络扩容 最小费用最大流+最大流+乱搞

1834: [ZJOI2010]network 网络扩容

Time Limit: 3 Sec Memory Limit: 64 MB

Submit: 2269 Solved: 1136

[Submit][Status][Discuss]

Description

给定一张有向图,每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求: 1、 在不扩容的情况下,1到N的最大流; 2、 将1到N的最大流增加K所需的最小扩容费用。

Input

输入文件的第一行包含三个整数N,M,K,表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W,表示一条从u到v,容量为C,扩容费用为W的边。

Output

输出文件一行包含两个整数,分别表示问题1和问题2的答案。

Sample Input

5 8 2

1 2 5 8

2 5 9 9

5 1 6 2

5 1 1 8

1 2 8 7

2 5 4 9

1 2 1 1

1 4 2 1

Sample Output

13 19

30%的数据中,N<=100

100%的数据中,N<=1000,M<=5000,K<=10

HINT

Source

Day1

这道题啊,似乎不是很复杂,起码省去了bt建图,充其量是个模板堆上,随便乱搞几行,直接正解。(ZJOI中最水的了吧??)

先按照读入连边。(第一问最大流时不需要费用,可以先存下来,为第二问准备)

Dinic模板一套,第一问A

在第一问的参与网络上,建边。

每两个点相连,边权为inf,费用为之前存下来的。

最后再建一个源,连向1,容量为k,费用为0

zkw模板一套,第二问A

。。。。。

code:(写的冗余QwQ)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define inf 0x7fffffff
struct data{
int from,to,next,c,v,co;
}edge[100010];
int q[100010],h,t;
int dis[100010];
int head[100010]={0},cnt=1;
bool visit[100010],mark[100010];
int n,m,k;
int S,T;
int ans; int read()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
} void add(int u,int v,int cap,int cost)
{
cnt++;edge[cnt].from=u;edge[cnt].to=v;
edge[cnt].v=cap;edge[cnt].co=cost;
edge[cnt].next=head[u];head[u]=cnt;
} void insert(int u,int v,int cap,int cost)
{
add(u,v,cap,cost);add(v,u,0,-cost);
} void add_edge(int u,int v,int cap,int cost)
{
cnt++;edge[cnt].from=u;edge[cnt].to=v;
edge[cnt].v=cap;edge[cnt].c=cost;
edge[cnt].next=head[u];head[u]=cnt;
} void insert_edge(int u,int v,int cap,int cost)
{
add_edge(u,v,cap,cost);add_edge(v,u,0,-cost);
} void init()
{
n=read();m=read();k=read();
for (int i=1; i<=m; i++)
{
int u,v,c,w;
u=read();v=read();c=read();w=read();
insert(u,v,c,w);
}
S=1;T=n;
} bool bfs()
{
memset(dis,-1,sizeof(dis));
q[1]=S;dis[S]=1;h=0;t=1;
while (h<t)
{
int j=q[++h],i=head[j];
while (i)
{
if (dis[edge[i].to]<0 && edge[i].v>0)
{
dis[edge[i].to]=dis[j]+1;
q[++t]=edge[i].to;
}
i=edge[i].next;
}
}
if (dis[T]>0) return true;
else return false;
} int dfs(int loc,int low)
{
if (loc==T) return low;
int w,used=0;
for (int i=head[loc]; i; i=edge[i].next)
{
if (edge[i].v>0 && dis[edge[i].to]==dis[loc]+1)
{
w=dfs(edge[i].to,min(low-used,edge[i].v));
edge[i].v-=w;edge[i^1].v+=w;
used+=w;if (used==low) return low;
}
}
if (!used) dis[loc]=-1;
return used;
} int dinic()
{
int tmp=0;
while (bfs())
{
tmp+=dfs(S,inf);
}
return tmp;
} void problem_1()
{
int tmp=dinic();
printf("%d ",tmp);
} void make()
{
int num=cnt;
for (int i=2; i<=num; i+=2)
insert_edge(edge[i].from,edge[i].to,inf,edge[i].co);
insert(0,1,k,0);
S=0;
} bool spfa()
{
memset(visit,0,sizeof(visit));
for (int i=S; i<=T; i++) dis[i]=inf;
h=0,t=1;
q[0]=T;visit[T]=1;dis[T]=0;
while (h<t)
{
int now=q[h];h++;visit[now]=0;
for (int i=head[now]; i; i=edge[i].next)
if (edge[i^1].v && dis[now]-edge[i].c<dis[edge[i].to])
{
dis[edge[i].to]=dis[now]-edge[i].c;
if (!visit[edge[i].to])
{
visit[edge[i].to]=1;
q[t++]=edge[i].to;
}
}
}
return dis[S]!=inf;
} int dfs1(int loc,int low)
{
mark[loc]=1;
if (loc==T) return low;
int w,used=0;
for (int i=head[loc]; i; i=edge[i].next)
if (dis[edge[i].to]==dis[loc]-edge[i].c && edge[i].v && !mark[edge[i].to])
{
w=dfs1(edge[i].to,min(low-used,edge[i].v));
ans+=w*edge[i].c;
edge[i].v-=w;edge[i^1].v+=w;
used+=w;if (used==low) return low;
}
return used;
} void zkw()
{
int tmp=0;
while (spfa())
{
mark[T]=1;
while (mark[T])
{
memset(mark,0,sizeof(mark));
tmp+=dfs1(S,inf);
}
}
} void problem_2()
{
make();
zkw();
printf("%d",ans);
} int main()
{
init();
problem_1();
problem_2();
return 0;
}
上一篇:VIJOS1476 旅行规划(树形Dp + DFS暴力乱搞)


下一篇:Oracle 自动生成hive建表语句