acdream 1017: Fast Transportation 网络流层次图

1017: Fast Transportation

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 72 Solved: 11

Description

I’m working for a huge transportation company, and this month we get a job that deliver K important 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. However 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.

(2 <= N <= 10, 1 <= M <= 20, 1 <= K <= 50, 1 <= S, T <= N, S != 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.

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

解题思路：

经典的网络流模型，层次图的应用。

对于最后要求的最短时间，由于单调性，可以使用二分答案的策略，仔细推算易知二分的上界是n + k。

对于每次枚举的天数S，将图中的每个点都拆成S个，则全图变成S层，我们规定同层之间不允许连边，对于原始图中的边(i,j),则在相邻两层中将对应的点从低的一层连上高的一层。设置超级源点，向第一层中的出发点连上一条容量为K的边，将每层中的目的地点想超级汇点连上一条容量无穷的边，然后压流验证。

虽然原始图中的点很少，但是分层后，网络中的点还是相当多的，所以需要较快的网络流算法进行验证。

SAP（shortest augment path） 20ms

View Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#define MIN(a,b) (a)<(b)?(a):(b)
const int inf = ~0u>>1;
int n, m, K, s, t, S, T, N;
int head[56666], h[56666], vh[56666], idx;
bool vis[56666], 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);
}

void input()
{
    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;
    }
}
void solve()
{
    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);
}
int main()
{
    while( scanf("%d%d%d%d%d", &n,&m,&K,&s,&t) != EOF)
    {
        input();
        solve();
    }
    return 0;
}

连续最短增广路算法-Dinic算法此题TLE

View Code

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<queue>
  6 #include<algorithm>
  7 #include<vector>
  8 using namespace std;
  9 #define MIN(a,b) (a)<(b)?(a):(b)
 10 const int inf = 0x3fffffff;
 11 
 12 int n, m, k, s, t, S, T, N;
 13 
 14 struct node{
 15     int v, f, nxt;
 16 }edge[30010];
 17 
 18 int head[10000],label[10000],idx;
 19 bool mp[20][20],vis[10000];
 20 queue<int> Q;
 21 void add( int u, int v,int f )
 22 {//成对添加,通过正向和反向相邻性质，用位异或快速运算
 23     edge[idx].v = v; edge[idx].f = f;
 24     edge[idx].nxt = head[u]; head[u] = idx++;
 25     edge[idx].v = u; edge[idx].f = 0;
 26     edge[idx].nxt = head[v]; head[v] = idx++;
 27 }
 28 
 29 void Input(){
 30     memset( mp, 0, sizeof(mp) );
 31     int u, v;
 32     for(int i = 0; i < m; i++)
 33     {
 34         scanf("%d%d", &u, &v);
 35         mp[u][v] = mp[v][u] = true;
 36     }
 37 }
 38 void CreateGraph( int x )
 39 {
 40     S = 0; T = (x+1)*n+1; N = (x+1)*n+2; idx = 0; //源点，汇点，总顶点数量
 41     memset( head, 0xff, sizeof(head));    
 42     
 43     for(int i = 1; i <= n; i++)
 44         for(int j = 1; j <= n; j++)
 45             if( mp[i][j] ) // (c-1)层i 与 c层j 联通 容量为1
 46                 for(int c = 1; c <= x; c++)
 47                     add( (c-1)*n+i, c*n+j, 1 );        
 48     for(int i = 1; i <= n; i++)
 49             for(int c = 1; c <= x; c++) // c-1层i 与 c层I 连通 容量为无穷大
 50                 add( (c-1)*n+i, c*n+i, inf ); 
 51     add( S, s, k ); //源点与第一层起点s连通 容量为k
 52     for(int c = 1; c <= x; c++) //汇点T与每一层的终点t连通 容量为无穷大
 53             add( c*n+t, T, inf );
 54 }
 55 bool BFS()
 56 {
 57     memset( label, 0, sizeof(label));
 58     memset( vis, 0, sizeof(vis));
 59     label[S] = 1;
 60     while( !Q.empty() ) Q.pop();
 61     Q.push( S ); vis[S] = true;
 62     while( !Q.empty() && !vis[T] )
 63     {
 64         int u = Q.front(); Q.pop();
 65         for(int i = head[u]; ~i; i = edge[i].nxt )
 66         {
 67             int v = edge[i].v;
 68             if( edge[i].f && !vis[v] ){ // 构建层次网络
 69                 vis[v] = true;    label[v] = label[u]+1;
 70                 Q.push( v );    
 71             } 
 72         }
 73     }
 74     return vis[T];
 75 }
 76 int DFS( int u, int flow ){
 77 //    printf("u = %d\n", u );
 78     int sum = 0;    
 79     if( u == T ) return flow;
 80     for(int i = head[u]; ~i; i = edge[i].nxt )
 81     {
 82         int v = edge[i].v;
 83         if( edge[i].f && label[v] == label[u]+1 )
 84         {
 85             int p = DFS( v, MIN(flow, edge[i].f) );
 86             edge[i].f -= p; edge[i^1].f += p;
 87             sum += p;
 88         }
 89     }
 90     return sum;
 91 }
 92 int dinic(){
 93     int maxflow = 0;
 94     while( BFS() ) maxflow += DFS( S, inf );
 95     return maxflow; 
 96 }
 97 void solve(){
 98     int l = 0, r = n*k;
 99     while( r > l ) //二分枚举天数mid
100     {
101         int mid = (r+l)>>1;// printf("mid = %d, l = %d, r = %d\n", mid, l, r );
102         CreateGraph( mid );
103         if( dinic() == k ) r = mid;//满足条件则继续缩短时间
104         else    l = mid+1;
105     }
106     printf("%d\n", l );
107 }
108 int main(){
109     while( scanf("%d%d%d%d%d",&n,&m,&k,&s,&t) != EOF)
110     {
111         Input();
112         solve();
113     }
114     return 0;
115 }

预流推进 PreFlow_Push 同样TLE

View Code

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<algorithm>
using namespace std;
const int inf = ~0u>>1;
#define MIN(a,b) (a)<(b)?(a):(b)
int n, m, K, s, t, S, T, N;
int head[30010],ef[30010],h[30010],idx;
bool mp[20][20], vis[30010]; 
struct Edge{
    int v, f, nxt;
}edge[500101];
struct node{
       int x;
       bool operator < (node tmp) const
       {
            return h[x] > h[ tmp.x ];
       }       
}qs,qt;
priority_queue< node > Q;
void AddEdge(int u, int v, int f)
{
    edge[idx].v = v; edge[idx].f = f;
    edge[idx].nxt = head[u]; head[u] = idx++;
    edge[idx].v = u; edge[idx].f = 0;
    edge[idx].nxt = head[v]; head[v] = idx++;
} 
void CreateGraph(int d)
{
    S = 0; T = (d+1)*n+1; N = (d+1)*n+2;
    memset(head,0xff,sizeof(head));idx = 0;    
    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+j, c*n+i, 1 );
    for(int i = 1; i <= n; i++)
        for(int c = 1; c <= d; c++)
            AddEdge( (c-1)*n+i, c*n+i, inf );
    for(int c = 1; c <= d; c++)
        AddEdge( c*n+t, T, inf );
    AddEdge( S, s, K );
}
bool Preflow_push()
{
    int maxflow = 0;
    memset( ef, 0, sizeof(ef));
    memset( h, 0, sizeof(h));
    memset( vis, 0, sizeof(vis));    
    ef[S] = inf; h[S] = N; 
    while( !Q.empty() ) Q.pop();
    qs.x = S; Q.push( qs ); vis[S] = true;
    while( !Q.empty() )
    {
        int u = (Q.top()).x; Q.pop(); 
        vis[u] = false;
    //    printf(" u = %d,h[u] = %d\n", u, h[u] );
        for(int i = head[u]; ~i ; i = edge[i].nxt )
        {
            int v = edge[i].v;
            int p = MIN( ef[u], edge[i].f );    
            if( p > 0 && (u == S || h[u] == h[v]+1)  )//层次图 
            {    
                edge[i].f -= p; edge[i^1].f += p; //更新残留网络    
                ef[u] -= p; ef[v] += p; //更新节点盈余值
                if( v == T ) maxflow += p;
                if( !vis[v] && v != S && v != T ){
                    vis[v] = true; 
                    qt.x = v; Q.push(qt); 
                }
            }
        }
        if( ef[u] > 0 && u != S && u != T )
        {
                h[u]++;
                vis[u] = true;
                qt.x = u; Q.push(qt); 
        }
    }
    return (maxflow == K);
}

void input(){
    int u, v;
    memset( mp, 0, sizeof(mp));    
    for(int i = 0; i < m; i++)
    {
        scanf("%d%d",&u,&v);
        mp[u][v] = mp[v][u] = true;
    }
}
void solve(){
    int l = 0, r = n*K;
    while( r > l ) //二分枚举天数
    {
        int mid = (r+l)>>1;
    //    printf("l = %d, r = %d, mid = %d\n", l, r, mid );    
        CreateGraph(mid);  
      //  l = r = mid;
        if( Preflow_push() ) r = mid;    
        else    l = mid+1;    
    }
    printf("%d\n", l );
}
int main(){
    while( scanf("%d%d%d%d%d", &n,&m,&K,&s,&t) != EOF)
    {
        input();
        solve();
    }
    return 0;
}