poj 2455(二分+最大流)

思路：求1-n的路径中最长段的最小值，显然要用到二分，我们二分最长段，如果当前u,v的距离小于等于limit,则连边（双向边），边容量为1，代表只能走1次。然后就是以1为源点，n为汇点跑最大流，如果maxflow>=T,则在（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 
 11 struct Edge{
 12     int v,cap,next;
 13 }edge[MAXM];
 14 
 15 struct E{
 16     int u,v,w;
 17 }e[MAXN*MAXN];
 18 
 19 int n,m,T,NE,NV;
 20 int head[MAXN];
 21 
 22 void Insert(int u,int v,int cap)
 23 {
 24     edge[NE].v=v;
 25     edge[NE].cap=cap;
 26     edge[NE].next=head[u];
 27     head[u]=NE++;
 28 
 29     edge[NE].v=u;
 30     edge[NE].cap=0;
 31     edge[NE].next=head[v];
 32     head[v]=NE++;
 33 }
 34 
 35 int level[MAXN],gap[MAXN];
 36 void bfs(int vt)
 37 {
 38     memset(level,-1,sizeof(level));
 39     memset(gap,0,sizeof(gap));
 40     level[vt]=0;
 41     gap[level[vt]]++;
 42     queue<int>que;
 43     que.push(vt);
 44     while(!que.empty()){
 45         int u=que.front();
 46         que.pop();
 47         for(int i=head[u];i!=-1;i=edge[i].next){
 48             int v=edge[i].v;
 49             if(level[v]<0){
 50                 level[v]=level[u]+1;
 51                 gap[level[v]]++;
 52                 que.push(v);
 53             }
 54         }
 55     }
 56 }
 57 
 58 int pre[MAXN],cur[MAXN];
 59 int SAP(int vs,int vt)
 60 {
 61     bfs(vt);
 62     memset(pre,-1,sizeof(pre));
 63     memcpy(cur,head,sizeof(head));
 64     int maxflow=0,aug=inf;
 65     int u=pre[vs]=vs;
 66     gap[0]=NV;
 67     while(level[vs]<NV){
 68         bool flag=false;
 69         for(int &i=cur[u];i!=-1;i=edge[i].next){
 70             int v=edge[i].v;
 71             if(edge[i].cap>0&&level[u]==level[v]+1){
 72                 flag=true;
 73                 pre[v]=u;
 74                 u=v;
 75                 aug=min(aug,edge[i].cap);
 76                 if(v==vt){
 77                     maxflow+=aug;
 78                     for(u=pre[v];v!=vs;v=u,u=pre[u]){
 79                         edge[cur[u]].cap-=aug;
 80                         edge[cur[u]^1].cap+=aug;
 81                     }
 82                     aug=inf;
 83                 }
 84                 break;
 85             }
 86         }
 87         if(flag)continue;
 88         int minlevel=NV;
 89         for(int i=head[u];i!=-1;i=edge[i].next){
 90             int v=edge[i].v;
 91             if(edge[i].cap>0&&level[v]<minlevel){
 92                 minlevel=level[v];
 93                 cur[u]=i;
 94             }
 95         }
 96         if(--gap[level[u]]==0)break;
 97         level[u]=minlevel+1;
 98         gap[level[u]]++;
 99         u=pre[u];
100     }
101     return maxflow;
102 }
103 
104 
105 void Build(int limit)
106 {
107     NE=0;
108     memset(head,-1,sizeof(head));
109     for(int i=1;i<=m;i++){
110         if(e[i].w<=limit){
111             Insert(e[i].u,e[i].v,1);
112             Insert(e[i].v,e[i].u,1);
113         }
114     }
115 }
116 
117 
118 int main()
119 {
120     int low,high,mid,MIN,limit,u,v,w;
121     while(~scanf("%d%d%d",&n,&m,&T)){
122         limit=0;
123         for(int i=1;i<=m;i++){
124             scanf("%d%d%d",&u,&v,&w);
125             e[i].u=u,e[i].v=v,e[i].w=w;
126             limit=max(limit,w);
127         }
128         NV=n;
129         low=0,high=limit+1,MIN=0;
130         while(low<=high){
131             mid=(low+high)>>1;
132             Build(mid);
133             if(SAP(1,n)>=T){
134                 MIN=mid;
135                 high=mid-1;
136             }else
137                 low=mid+1;
138         }
139         printf("%d
",MIN);
140     }
141     return 0;
142 }
View Code