网络流 1009
Optimal Milking Time Limit : 4000/2000ms (Java/Other) Memory Limit : 60000/30000K (Java/Other)Total Submission(s) : 5 Accepted Submission(s) : 2Problem DescriptionInputOutputSample InputSample Output#include<iostream>#include<algorithm>#include<cstdio>#include<cstring>#define max(a,b) ((a)>(b)?(a):(b))using namespace std;const int N=420;const int M=82000;const int INF=99999999;int n;int gap[N],dis[N],pre[N],head[N],cur[N];int map[N][N];int NE,NV;struct Node{ int pos,next; int c;} E[M];#define FF(i,NV) for(int i=0;i<NV;i++)int sap(int s,int t){ memset(dis,0,sizeof(int)*(NV+1)); memset(gap,0,sizeof(int)*(NV+1)); FF(i,NV) cur[i] = head[i]; int u = pre[s] = s,maxflow = 0; int aug =INF; gap[0] = NV; while(dis[s] < NV) {loop: for(int &i = cur[u]; i != -1; i = E[i].next) { int v = E[i].pos; if(E[i].c && dis[u] == dis[v] + 1) { aug=min(aug,E[i].c); pre[v] = u; u = v; if(v == t) { maxflow += aug; for(u = pre[u]; v != s; v = u,u = pre[u]) { E[cur[u]].c -= aug; E[cur[u]^1].c += aug; } aug =INF; } goto loop; } } if( (--gap[dis[u]]) == 0) break; int mindis = NV; for(int i = head[u]; i != -1 ; i = E[i].next) { int v = E[i].pos; if(E[i].c && mindis > dis[v]) { cur[u] = i; mindis = dis[v]; } } gap[ dis[u] = mindis+1 ] ++; u = pre[u]; } return maxflow;}void addEdge(int u,int v,int c ){ E[NE].c = c; E[NE].pos = v; E[NE].next = head[u]; head[u] = NE++; E[NE].c = 0; E[NE].pos = u; E[NE].next = head[v]; head[v] = NE++;}int ans;void floyed(){ for(int k=1; k<=n; k++) for(int i=1; i<=n; i++) { if(map[i][k]!=INF) { for(int j=1; j<=n; j++) { if(map[k][j]!=INF&&map[i][j]>map[i][k]+map[k][j]) { map[i][j]=map[i][k]+map[k][j]; ans=max(map[i][j],ans); } } } }}int main(){ int k,c,m; while(cin>>k>>c>>m) { ans=-1; n=k+c; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { cin>>map[i][j]; //ans=max(ans,map[i][j]); if(map[i][j]==0) map[i][j]=INF; } floyed(); int low=0,high=ans,mid; //high的值应该最小为所有点对之间路径中最长的，不是初始时中的最大值， //由于这个原因wa了几次。…… while(low<=high) { NE=0; NV=k+c+2; memset(head,-1,sizeof(head)); mid=(low+high)/2; for(int i=1;i<=k;i++) addEdge(i,k+c+1,m); for(int i=k+1;i<=k+c;i++) addEdge(0,i,1); for(int i=k+1;i<=k+c;i++)//牛与机器建边 for(int j=1;j<=k;j++) { if(map[i][j]<=mid) addEdge(i,j,1); } if(sap(0,k+c+1)==c)//mid符合条件，则可以减小。 high=mid-1; else low=mid+1; } cout<<low<<endl; } return 0;}/*2 3 20 3 2 1 13 0 3 2 02 3 0 1 01 2 1 0 21 0 0 2 0*/