ACdream 1017 Fast Transportation （网络流+分层图）

你的名字 2022-07-15 04:59 150阅读 0赞

### Fast Transportation ###

Time Limit: 2000/1000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

[Submit][] [Statistic][] [Next Problem][]

#### Problem Description ####

I’m working for a huge transportation company, and this month we get a job that deliver Kimportant medicinal machines from city S to city T. Since the machines is so large that for each machine we should use a whole truck to carry it.

We live in a country contains N cities and M bidirectional roads, each road cost one day to passed. And your boss wants you, the best programmer, to find a plan which can deliver all machines in fewest days.

However with the unknown reasons, we can just use each road only once a day.

Sometimes a truck can choose not to go but wait at a city.

A city can hold any truck each day.

#### Input ####

There are multiple test cases.

In each test case, the first line contains five integers N, M, K, S and T.  
Next M lines each line contains two integers a, b, indicating a road connected the city a and city b.  
There is at most one road in any two cities, and no road connected one city to itself.

2 ≤ N ≤ 10, 1 ≤ M ≤ 20

1 ≤ K ≤ 50, 1 ≤ S, T ≤ N, S != T

#### Output ####

For each test, please output an integer indicating the fewest days to deliver all machine to the destination.

#### Sample Input ####

6 7 4 1 6
    1 2
    2 3
    3 5
    5 6
    1 4
    4 6
    4 3

#### Sample Output ####

#### Hint ####

The road can be traveled in both directions, but remember that each day only one truck can travel through it, in particular, two trucks cannot simultaneously travel the same road in opposite directions

#### Source ####

dut200901102

#### Manager ####

[nanae][]

题意：给定一个无向图，求要用最少的时间从源点S向终点T运送K件货物。要求：  
（1）从一个节点走到相邻节点用时1天；  
（2）一天中一条路只能使用一次。

题解：对于最后要求的最短时间，由于单调性，可以使用二分答案的策略。对于每次枚举的天数S，将图中的每个点都拆成S个，则全图变成S层（分层图）。规定同层之间不允许连边，对于原始图中的边(i,j),则在相邻两层中将对应的点从低的一层连上高的一层。设置超级源点，向第一层中的出发点连上一条容量为K的边，将每层中的目的地点向超级汇点连上一条容量无穷的边，然后求最大流是否等于K。我用了SAP。可以Dinic.....或者ISAP......

AC代码：

#include<bits/stdc++.h>
    using namespace std;
    const int inf = 1e9;
    int n,m,K,s,t,S,T,N;
    int head[50010],h[50010],vh[50010];
    int idx;
    bool vis[50010],mp[120][120];
    
    struct Edge
    {
        int v, f, next;
        
    }edge[501010];
    
    void addEdge(int u,int v,int f)
    {
        edge[idx].v = v; edge[idx].f = f;
        edge[idx].next = head[u]; head[u] = idx++;
        edge[idx].v = u; edge[idx].f = 0;
        edge[idx].next = head[v]; head[v] = idx++;
    }
    void CreateGraph(int d)
    {
        memset( head, 0xff, sizeof(head)); 
    	idx = 0;
        S = 0; 
    	T = (d+1)*n+1; 
    	N = (d+1)*n+2;
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                if(mp[i][j])
                    for(int c = 1; c <= d; c++)
                        addEdge( (c-1)*n+i,c*n+j, 1 );    
                        
        for(int i = 1; i <= n; i++)
            for(int c = 1; c <= d; c++)
                addEdge( (c-1)*n+i, c*n+i, inf );
                
        addEdge( S, s, K );
        for(int c = 1; c <= d; c++)
            addEdge( c*n+t, T, inf );
    }  
    int DFS( int u, int flow )
    {
        if( u == T ) return flow;
        int tmp = h[u]+1, remain = flow;
        for(int i = head[u]; ~i; i = edge[i].next )
        {
            int v = edge[i].v;
            if( edge[i].f && h[u] == h[v]+1 )
            {
                int p = DFS( v, min( remain, edge[i].f ) ); //取修改后的可流动流量递归,部分优化
                edge[i].f -= p; 
    			edge[i^1].f += p; 
    			remain -= p;
                if( !remain || h[S] == N ) return flow - remain; //若流量为0或者无增广路则退出
            }
        }
        for(int i = head[u]; ~i; i = edge[i].next )
        {
        	if( edge[i].f )  
    		tmp = min( tmp, h[ edge[i].v ] );
    	}
            
        if( !( --vh[ h[u] ] ) ) h[S] = N; //更新完顶点u后,v[u]层节点数减少一个
        else  vh[ h[u]=tmp+1 ]++; //间隙优化,若出现断层,即可判定无增广路
        return flow - remain;
    }
    bool sap()
    {
        int maxflow = 0;
        memset( h, 0, sizeof(h)); // 层次网络
        memset( vh, 0, sizeof(vh)); // 当前层节点数量
        vh[0] = N;  // 0层节点数量初始化为 总结数N个
        while( h[S] < N ) // 起点层次大于等于N时无增广路
            maxflow += DFS( S, inf );  // 从源点S 开始找增广路,初始流量为inf
        return (maxflow == K);
    }
      
    int main()
    {
    	while(~scanf("%d%d%d%d%d",&n,&m,&K,&s,&t))
    	{
    		memset(mp,0,sizeof(mp));
    		int u,v;
    		for(int i=0;i<m;i++)
    		{
    			scanf("%d%d",&u,&v);
    			mp[u][v]=mp[v][u]=true;
    		}
    		 int l=0, r=n*K;
    		 while(r>l)
    		 {
    		 	int mid=(l+r)>>1;
    		 	CreateGraph(mid);
    		 	if(sap()) r=mid;
    		 	else l=mid+1;
    		 }
    		 printf("%d\n",l);
    	}
    	return 0;
    }

[Submit]: http://acdream.info/submit?pid=1017
[Statistic]: http://acdream.info/statistic/1017
[Next Problem]: http://acdream.info/problem?pid=1018
[nanae]: http://acdream.info/user/nanae