poj 2391(二分+最大流)

思路：求最短时间,可以想到二分,然后判断可行性。首先在原图上求 floyd,得到每两个棚之间的最短距离。然后拆点:将每个棚拆为 i 和 i’(流进和流出),添边(i,i’,INF)。增加源点 s 和汇点 t,从 s 连边到 i,容量为该棚现在的猫的数量,i’连边到 t,容量为该棚的容量。若棚 i 和棚 j 之间的距离不大于 limit,则连边(i,j’,INF), (j,i’,INF)。求最大流,若从 s 发出的边均满流,则在 low 和 mid 中搜索;否则在 mid 和 high 中搜索。

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<algorithm>
  5 #include<queue>
  6 using namespace std;
  7 #define MAXN 444
  8 #define MAXM 44444444
  9 #define inf 1<<30
 10 #define INF 1LL<<60
 11 
 12 struct Edge{
 13     int v,cap,next;
 14 }edge[MAXM];
 15 
 16 int n,m,NE,vs,vt,NV;
 17 int head[MAXN];
 18 
 19 void Insert(int u,int v,int cap)
 20 {
 21     edge[NE].v=v;
 22     edge[NE].cap=cap;
 23     edge[NE].next=head[u];
 24     head[u]=NE++;
 25 
 26     edge[NE].v=u;
 27     edge[NE].cap=0;
 28     edge[NE].next=head[v];
 29     head[v]=NE++;
 30 }
 31 
 32 int level[MAXN],gap[MAXN];
 33 void bfs(int vt)
 34 {
 35     memset(level,-1,sizeof(level));
 36     memset(gap,0,sizeof(gap));
 37     level[vt]=0;
 38     gap[level[vt]]++;
 39     queue<int>que;
 40     que.push(vt);
 41     while(!que.empty()){
 42         int u=que.front();
 43         que.pop();
 44         for(int i=head[u];i!=-1;i=edge[i].next){
 45             int v=edge[i].v;
 46             if(level[v]<0){
 47                 level[v]=level[u]+1;
 48                 gap[level[v]]++;
 49                 que.push(v);
 50             }
 51         }
 52     }
 53 }
 54 
 55 int pre[MAXN],cur[MAXN];
 56 int SAP(int vs,int vt)
 57 {
 58     bfs(vt);
 59     memset(pre,-1,sizeof(pre));
 60     memcpy(cur,head,sizeof(head));
 61     int maxflow=0,aug=inf;
 62     int u=pre[vs]=vs;
 63     gap[0]=NV;
 64     while(level[vs]<NV){
 65         bool flag=false;
 66         for(int &i=cur[u];i!=-1;i=edge[i].next){
 67             int v=edge[i].v;
 68             if(edge[i].cap>0&&level[u]==level[v]+1){
 69                 flag=true;
 70                 pre[v]=u;
 71                 u=v;
 72                 aug=min(aug,edge[i].cap);
 73                 if(v==vt){
 74                     maxflow+=aug;
 75                     for(u=pre[v];v!=vs;v=u,u=pre[u]){
 76                         edge[cur[u]].cap-=aug;
 77                         edge[cur[u]^1].cap+=aug;
 78                     }
 79                     aug=inf;
 80                 }
 81                 break;
 82             }
 83         }
 84         if(flag)continue;
 85         int minlevel=NV;
 86         for(int i=head[u];i!=-1;i=edge[i].next){
 87             int v=edge[i].v;
 88             if(edge[i].cap>0&&level[v]<minlevel){
 89                 minlevel=level[v];
 90                 cur[u]=i;
 91             }
 92         }
 93         if(--gap[level[u]]==0)break;
 94         level[u]=minlevel+1;
 95         gap[level[u]]++;
 96         u=pre[u];
 97     }
 98     return maxflow;
 99 }
100 
101 int now_num[MAXN],num[MAXN];
102 long long dist[MAXN][MAXN];
103 void Floyd()
104 {
105     for(int k=1;k<=n;k++)
106         for(int i=1;i<=n;i++)
107             for(int j=1;j<=n;j++)
108                 if(dist[i][k]<INF&&dist[k][j]<INF&&dist[i][k]+dist[k][j]<dist[i][j])
109                     dist[i][j]=dist[i][k]+dist[k][j];
110 }
111 
112 void Build(long long limit)
113 {
114     NE=0;
115     memset(head,-1,sizeof(head));
116     vs=0,vt=2*n+1,NV=2*n+2;
117     for(int i=1;i<=n;i++)Insert(vs,i,now_num[i]);
118     for(int i=1;i<=n;i++)Insert(i+n,vt,num[i]);
119     for(int i=1;i<=n;i++)Insert(i,i+n,inf);
120     for(int i=1;i<=n;i++){
121         for(int j=i+1;j<=n;j++){
122             if(dist[i][j]<=limit){
123                 Insert(i,j+n,inf);
124                 Insert(j,i+n,inf);
125             }
126         }
127     }
128 }
129 
130 int main()
131 {
132     int u,v,sum;
133     long long w,low,high,mid,ans,limit;
134     while(~scanf("%d%d",&n,&m)){
135         limit=sum=0;
136         for(int i=1;i<=n;i++){
137             scanf("%d%d",&now_num[i],&num[i]);
138             sum+=now_num[i];
139         }
140         for(int i=1;i<=n;i++)
141             for(int j=1;j<=n;j++)
142                 dist[i][j]=(i==j)?0:INF;
143         while(m--){
144             scanf("%d%d%lld",&u,&v,&w);
145             limit+=w;
146             if(dist[u][v]>w){
147                 dist[u][v]=dist[v][u]=w;
148             }
149         }
150         Floyd();
151         low=0,high=limit+1,mid,ans=-1;
152         while(low<=high){
153             mid=(low+high)>>1;
154             Build(mid);
155             if(SAP(vs,vt)==sum){
156                 ans=mid;
157                 high=mid-1;
158             }else
159                 low=mid+1;
160         }
161         printf("%lld
",ans);
162     }
163     return 0;
164 }

View Code