poj 2112 floyd + Dinic 최대 흐름 + 2 분 최소 값

제목 의 대 의 는:
K 대 착 유기 계, C 두 우, K 는 30 을 넘 지 않 고 C 는 200 을 넘 지 않 는 다. 각 착 유기 계 는 최대 M 대 소 를 위해 일 할 수 있다. 이 소 와 기계 사이, 소 와 소 사이, 기계 와 기계 사이 의 거 리 를 제시 하고 가장 많은 소 가 기계 로 젖 을 짤 수 있 도록 하 는 상황 에서 그 중에서 가장 긴 소 한 마리 의 이동 거 리 를 최소 화한 다.
먼저 Floyd 로 임의의 두 점 사이 의 최 단 거 리 를 구하 고 이분법 으로 가장 많은 이동 거리 d 를 제한한다. 최대 흐름 을 구 할 때 증폭 로 를 검색 할 때 거리 가 d 를 초과 하 는 지 판단 하면 된다.
 

  1 #include <cstdio>

  2 #include <cstring>

  3 #include <queue>

  4 #define _clr(x, y) memset(x, y, sizeof(x))

  5 #define Min(x, y) (x < y ? x : y)

  6 #define INF 0x3f3f3f3f

  7 #define N 1005

  8 using namespace std;

  9 

 10 int flow[N][N], dist[N][N];

 11 int level[N];

 12 int K, C, M,  S, T, ln;

 13 

 14 void Floyd()

 15 {

 16     for(int k=1; k<=ln; k++)

 17         for(int i=1;i<=ln; i++) if(dist[i][k]<INF)

 18             for(int j=1; j<=ln; j++)

 19                 if(dist[i][k]+dist[k][j]<dist[i][j])

 20                     dist[i][j] = dist[i][k]+dist[k][j];

 21 }

 22 

 23 bool bfs()

 24 {

 25     _clr(level, -1);

 26     level[S] = 0;

 27     queue<int> Q;

 28     Q.push(S);

 29     while(!Q.empty())

 30     {

 31         int u = Q.front();

 32         Q.pop();

 33         for(int i=0; i<=T; i++)

 34         {

 35             if(flow[u][i] && level[i]<0)

 36             {

 37                 level[i] = level[u] + 1;

 38                 Q.push(i);

 39             }

 40         }

 41     }

 42     return level[T]> 0 ? 1 : 0;

 43 }

 44 

 45 int dfs(int x, int f)

 46 {

 47     int a;

 48     if(x==T) return f;

 49     for(int i=0; i<=T; i++)

 50     {

 51         if(flow[x][i] && level[i]==level[x]+1 && (a=dfs(i,Min(f,flow[x][i]))))

 52         {

 53             flow[x][i] -= a;

 54             flow[i][x] += a;

 55             return a;

 56         }

 57     }

 58     level[x] = -1;

 59     return 0;

 60 }

 61 

 62 __int64 Dinic(int len)

 63 {       

 64     //          

 65     _clr(flow, 0);

 66     for(int i=1; i<=K; i++)

 67         flow[S][i] = M;

 68     for(int i=K+1; i<=ln; i++)

 69         flow[i][T] = 1;

 70     for(int i=1; i<=K; i++)   //   

 71         for(int j=K+1; j<=ln; j++)  //   

 72             flow[i][j] = (dist[i][j]<=len);

 73 

 74     //           

 75     __int64 ans=0, a=0;

 76     while(bfs())

 77         while(a=dfs(0,INF)) ans += a;

 78     return ans;

 79 }

 80 

 81 //              

 82 int Slove()

 83 {

 84     int l=1, r=100000;

 85     while(l<=r)

 86     {

 87         int mid = (l+r)>>1;

 88         if(Dinic(mid)>=C) r = mid-1;

 89         else l = mid+1;

 90     }

 91     return l;

 92 }

 93 int main()

 94 {

 95     while(~scanf("%d%d%d", &K, &C, &M))

 96     {

 97         ln = K+C;

 98         T = ln + 1;

 99         _clr(dist, 0);

100         for(int i=1; i<=ln; i++)

101             for(int j=1; j<=ln; j++)

102             {

103                 scanf("%d", dist[i]+j);

104                 if(dist[i][j]==0) dist[i][j]=INF;

105             }

106         ////               

107         Floyd();

108 

109         printf("%d
", Slove());

110     }

111     return 0;

112 }