中石油4215: Water（dinic网络流，深度优化）

http://exam.upc.edu.cn/problem.php?id=4215

4215: Water

时间限制: 1 Sec  内存限制: 128 MB

提交: 49  解决: 12

[提交][状态][讨论版]

题目描述

A water company is trying to provide water from its pumping station to a mansion. The company owns n water stations, numbered 1..n, which are connected by a variety of pipes. Water can flow through both directions of a pipe, but the total amount of water that can flow through the pipe is bounded by the capacity of the pipe.
The water company is constantly improving the pipes, increasing the capacity of various pipes. The water company is conducting k improvements (each of which is permanent after it is executed). An improvement consists of taking a pipe between two locations and increasing its capacity by a fixed amount, or installing a pipe between two locations which are not directly connected by a pipe.
After each improvement, the water company wants to know the maximum amount of water the mansion could receive.

输入

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input contains three integers, n (2≤n≤100), p (0≤p≤ n(n-1)/2), and k (1≤k≤10,000), where n is the number of stations, p is the number of initial pipes, and k is the number of improvements. The first station in the list is always the pumping station, and the second is always the mansion.
The next p lines will describe the pipes in the initial setup. The lines will each contain three integers, a, b (1≤a<b≤n) and c (1≤c≤1,000), which indicates that stations a and b are connected by a pipe with capacity c. No (a,b) pair will appear more than once in this section.
The next k lines will describe the improvements. The lines will each contain three integers, a, b (1≤a<b≤n) and c (1≤c≤1,000), which indicates that the pipe connecting stations a and b has its capacity increased by c (if there is currently no pipe between a and b, then one is created with capacity c). Note that it is possible for an (a,b) pair to be repeated in this section.

输出

Output k+1 integers, each on its own line, describing the maximum amount of water that can reach the mansion. The first number is the amount of water reaching the mansion in the initial configuration. The next k numbers are the amounts of water reaching the mansion after each improvement.

样例输入

3 2 1
1 3 10
2 3 1
2 3 15

样例输出

1
10

【解析】；这题套网络流dinic跑最大流应该是没问题的，但超时很拿人。竟然还有这种优化。

cur数组可以说是大功臣，有了这个数组，立马不超时了。

cur数组的作用是记录dfs时，扫描的起始点，不必每次都从1开始扫描，而是从cur[u]开始！

【代码】：

#include <stdio.h>  
#include <string.h>
#include <algorithm>   
#include <queue>   
#define mset(a,i) memset(a,i,sizeof(a))
using namespace std;  
typedef long long ll;  
const int INF=0x3f3f3f3f;  
const int MAX=1e6+5;  
int n,m,k;
int dep[220];//节点的标号
int cur[220];//dfs的优化数组 
int Map[220][220];
int BFS(int s,int t)  
{  
    mset(dep,-1);  
    dep[s]=0;
    queue<int>q;
    q.push(s);
    while(!q.empty())  
    {  
        int u=q.front();q.pop();  
        if(u==t)return 1;
        for(int t=1;t<=n;t++)
        {  
            if(dep[t]<0&&Map[u][t]){  
                dep[t]=dep[u]+1;
                q.push(t);
            }  
        } 
    }  
    return dep[t]!=-1; 
}  
int dfs(int s,int t,int low=INF)
{  
    if(s==t)return low;
    int cap;
    for(int &v=cur[s];v<=n;v++)
    { 
        if(Map[s][v]&&dep[v]==dep[s]+1&&(cap=dfs(v,t,min(low,Map[s][v]))))  
        {  
        	Map[s][v]-=cap;
        	Map[v][s]+=cap;
            return cap;
        }  
    }
    return 0;
}  
int dinic(int s,int t)
{  
    int temp,ans=0;  
    while(BFS(s,t))  
    {
    	for(int i=1;i<=n;i++)cur[i]=1;//非常牛逼的优化 
        ans+=dfs(s,t);
    }
    return ans;  
}  
int main()  
{
    int s,t,l;  
    while(~scanf("%d%d%d",&n,&m,&k))//m边，n点  
    {
        mset(Map,0);
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d",&s,&t,&l);
            Map[s][t]=l;
			Map[t][s]=l;
        }  
        int ans=dinic(1,2);
       	printf("%d\n",ans);
        while(k--)
        {
            scanf("%d%d%d",&s,&t,&l);
            Map[s][t]+=l;
			Map[t][s]+=l;
	        ans+=dinic(1,2);
	        printf("%d\n",ans);
		}
    }  
    return 0;  
}