1834: [ZJOI2010]network 网络扩容

Time Limit: 3 Sec  

Memory Limit: 64 MB

Submit: 3394  

Solved: 1774

[ ][ ][ ]

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

首先T1打板就好了

本题难点在T2，如何最小费用扩展网络？

其实就是最小费用流嘛

我们对所有的原边再加一条流量无限的费用为w的边，再加一个超级源指向源点，容量K费用0

再跑一遍费用流就好了

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define LL long long int#define REP(i,n) for (int i = 1; i <= (n); i++)#define Redge(u) for (int k = head[u]; k != -1; k = edge[k].next)using namespace std;const int maxn = 1005,maxm = 30005,INF = 1000000000;inline int RD(){	int out = 0,flag = 1; char c = getchar();	while (c < 48 || c > 57) {if (c == '-') flag = -1; c = getchar();}	while (c >= 48 && c <= 57) {out = (out << 1) + (out << 3) + c - '0'; c = getchar();}	return out * flag;}int N,M,K,head[maxn],nedge = 0,d[maxn],cur[maxn],S,T,p[maxn],f[maxn];bool vis[maxn];struct EDGE{int from,to,f,w,next;}edge[maxm];inline void build(int u,int v,int f,int w){	edge[nedge] = (EDGE){u,v,f,w,head[u]}; head[u] = nedge++;	edge[nedge] = (EDGE){v,u,0,-w,head[v]}; head[v] = nedge++;}bool bfs(){	queue
         
           q; REP(i,N) vis[i] = false,d[i] = INF; vis[S] = true; d[S] = 0; q.push(S); int u,to; while (!q.empty()){ u = q.front(); q.pop(); Redge(u) if (edge[k].f && !vis[to = edge[k].to]){ d[to] = d[u] + 1; vis[to] = true; q.push(to); } } return vis[T];}int dfs(int u,int minf){ if (u == T || !minf) return minf; int flow = 0,f,to; if (cur[u] == -2) cur[u] = head[u]; for (int& k = cur[u]; k != -1; k = edge[k].next) if (d[to = edge[k].to] == d[u] + 1 && (f = dfs(to,min(minf,edge[k].f)))){ edge[k].f -= f; edge[k ^ 1].f += f; flow += f; minf -= f; if (!minf) break; } return flow;}int maxflow(){ int flow = 0; while (bfs()){fill(cur,cur + maxn,-2); flow += dfs(S,INF);} return flow;}int mincost(){ int cost = 0,flow = 0; while (true){ queue
          
            q; for (int i = 0; i <= N; i++) d[i] = INF,vis[i] = false; d[S] = 0; f[S] = INF; p[S] = 0; q.push(S); int to,u; while (!q.empty()){ u = q.front(); q.pop(); vis[u] = false; Redge(u) if (edge[k].f && d[to = edge[k].to] > d[u] + edge[k].w){ d[to] = d[u] + edge[k].w; p[to] = k; f[to] = min(f[u],edge[k].f); if (!vis[to]) q.push(to),vis[to] = true; } } if (d[T] == INF) break; flow += f[T]; cost += f[T] * d[T]; u = T; while (u != S){ edge[p[u]].f -= f[T]; edge[p[u] ^ 1].f += f[T]; u = edge[p[u]].from; } } return cost;}int main(){ memset(head,-1,sizeof(head)); N = RD(); M = RD(); K = RD(); S = 1; T = N; int a,b,f,w; while (M--){ a = RD(); b = RD(); f = RD(); w = RD(); build(a,b,f,w); } int ans1 = maxflow(),ans2,E = nedge; for (int i = 0; i < E; i += 2){ build(edge[i].from,edge[i].to,INF,edge[i].w); edge[i].w = edge[i ^ 1].w = 0; } S = 0; build(S,1,K,0); ans2 = mincost(); cout<
           
            <<' '<
            
             <