bzoj1733[Usaco2005 feb]Secret Milking Machine 神秘的挤奶机*

bzoj1733[Usaco2005 feb]Secret Milking Machine 神秘的挤奶机

题意：

n点无向图。要从1走到nT次，问不重复经过每条路的方案中最长路径长度的最小值。n≤200，边权≤1000000。

题解：

二分答案，然后只插入权值不超过二分值的边，跑最大流。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <queue>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 40010
 7 #define INF 0x3fffffff
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 struct e{int t,c,n;}es[maxn*4]; int g[maxn],ess;
17 void pe(int f,int t,int c){es[++ess]=(e){t,c,g[f]}; g[f]=ess; es[++ess]=(e){f,0,g[t]}; g[t]=ess;}
18 void init(){memset(g,0,sizeof(g)); ess=1;}
19 int n,p,k,f[maxn],t[maxn],w[maxn],l,r,ans;
20 queue<int>q; int h[maxn];
21 bool bfs(int s,int t){
22     while(!q.empty())q.pop(); memset(h,-1,sizeof(h)); h[s]=0; q.push(s);
23     while(!q.empty()){
24         int x=q.front(); q.pop();
25         for(int i=g[x];i;i=es[i].n)if(h[es[i].t]==-1&&es[i].c){h[es[i].t]=h[x]+1; q.push(es[i].t);}
26     }
27     return h[t]!=-1;
28 }
29 int dfs(int x,int t,int f){
30     if(x==t)return f; int w,u=0;
31     for(int i=g[x];i;i=es[i].n)if(h[es[i].t]==h[x]+1&&es[i].c){
32         w=dfs(es[i].t,t,min(f,es[i].c)); f-=w; u+=w; es[i].c-=w; es[i^1].c+=w; if(!f)return u;
33     }
34     if(!u)h[x]=-1; return u;
35 }
36 int dinic(int x){
37     init(); inc(i,1,p)if(w[i]<=x)pe(f[i],t[i],1),pe(t[i],f[i],1); int f=0;
38     while(bfs(1,n))f+=dfs(1,n,INF); return f;
39 }
40 int main(){
41     n=read(); p=read(); k=read(); inc(i,1,p)f[i]=read(),t[i]=read(),w[i]=read(); l=0; r=1000000;
42     while(l<=r){
43         int mid=(l+r)>>1; if(dinic(mid)>=k)ans=mid,r=mid-1;else l=mid+1;
44     }
45     printf("%d",ans); return 0;
46 }

20161018