POJ 2112 Optimal Milking(最大流+二分)

21762 ワード

タイトルリンク
dinicテンプレートをテストして、このテンプレートが正しいかどうか分かりませんが、その問題はこのdinicでは通れません.最適化を加えるとWAになり,最適化TLEを加えない.
  1 #include <cstdio>

  2 #include <string>

  3 #include <cstring>

  4 #include <queue>

  5 #include <map>

  6 #include <algorithm>

  7 using namespace std;

  8 #define INF 0x3ffffff

  9 struct node

 10 {

 11     int u,v,next,re,w;

 12 } edge[200001];

 13 int first[501],dis[501];

 14 int p[251][251];

 15 int t;

 16 int sv,ev,K,C,M;

 17 void CL()

 18 {

 19     t = 1;

 20     memset(first,-1,sizeof(first));

 21 }

 22 void add(int u,int v,int w)

 23 {

 24     edge[t].u = u;

 25     edge[t].v = v;

 26     edge[t].w = w;

 27     edge[t].re = t+1;

 28     edge[t].next = first[u];

 29     first[u] = t++;

 30     edge[t].u = v;

 31     edge[t].v = u;

 32     edge[t].w = 0;

 33     edge[t].re = t-1;

 34     edge[t].next = first[v];

 35     first[v] = t ++;

 36 }

 37 int bfs()

 38 {

 39     int u,v,i;

 40     memset(dis,0xff,sizeof(dis));

 41     queue<int> que;

 42     que.push(sv);

 43     dis[sv] = 0;

 44     while(!que.empty())

 45     {

 46         u = que.front();

 47         que.pop();

 48         for(i = first[u]; i != -1; i = edge[i].next)

 49         {

 50             v = edge[i].v;

 51             if(edge[i].w > 0&&dis[v] < 0)

 52             {

 53                 dis[v] = dis[u] + 1;

 54                 que.push(v);

 55             }

 56         }

 57     }

 58     if(dis[ev] > 0) return 1;

 59     else return 0;

 60 }

 61 int dfs(int u,int step)

 62 {

 63     int i,a = 0,v,flag = 0;

 64     if (u == ev) return step;

 65     for (i = first[u];i != -1&&flag < step; i = edge[i].next)//flag<step

 66     {

 67         v = edge[i].v;

 68         if (edge[i].w > 0&& dis[v] == dis[u]+1&&(a = dfs(v,min(step,edge[i].w))))

 69         {

 70             edge[i].w -= a;

 71             flag += a;// 

 72             edge[edge[i].re].w += a;

 73             return a;

 74         }

 75     }

 76     if(flag == 0) dis[u] = -1;// 

 77     return flag;

 78 }

 79 void build(int x)

 80 {

 81     int i,j;

 82     CL();

 83     for(i = 1; i <= K; i ++)

 84     {

 85         add(0,i,M);

 86     }

 87     for(i = 1; i <= K; i ++)

 88     {

 89         for(j = 1; j <= C; j ++)

 90         {

 91             if(p[i][j+K] <= x)

 92             add(i,K+j,1);

 93         }

 94     }

 95     for(i = 1;i <= C;i ++)

 96     {

 97         add(i+K,ev,1);

 98     }

 99 }

100 int fun(int x)

101 {

102     int ans = 0,res;

103     build(x);

104     while(bfs())

105     {

106           while(res=dfs(sv,INF))

107           ans += res;

108     }

109     if(ans == C)

110         return 1;

111     else

112         return 0;

113 }

114 int bin(int l,int r)

115 {

116     int str,mid,end;

117     str = l;

118     end = r;

119     while(str < end)

120     {

121         mid = (str + end)/2;

122         if(fun(mid))

123         {

124             end = mid;

125         }

126         else

127         {

128            str = mid + 1;

129         }

130     }

131     return end;

132 }

133 int main()

134 {

135     int i,j,k;

136     while(scanf("%d%d%d",&K,&C,&M)!=EOF)

137     {

138         for(i = 1;i <= K+C;i ++)

139         {

140             for(j = 1;j <= K+C;j ++)

141             {

142                 scanf("%d",&p[i][j]);

143                 if(i != j&&p[i][j] == 0)

144                 p[i][j] = INF;

145             }

146         }

147         for(i = 1;i <= K+C;i ++)

148         {

149             for(j = 1;j <= K+C;j ++)

150             {

151                 for(k = 1;k <= K+C;k ++)

152                 {

153                     if(p[j][k] > p[j][i] + p[i][k])

154                     p[j][k] = p[j][i] + p[i][k];

155                 }

156             }

157         }

158         sv = 0;

159         ev = K+C+1;

160         int maxz = 0;

161         for(i = 1;i <= K+C;i ++)

162         {

163             for(j = 1;j <= K+C;j ++)

164             maxz = max(maxz,p[i][j]);

165         }

166         printf("%d
",bin(0,maxz)); 167 } 168 return 0; 169 }