POJ 2455 Secret Milking Machine （Dinic + 二分 或 二分+SAP）

dinggela

Secret Milking Machine

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 7681		Accepted: 2340

Description


Farmer John is constructing a new milking machine and wishes to keep it secret as long as possible. He has hidden in it deep within his farm and needs to be able to get to the machine without being detected. He must make a total of T (1 <= T <= 200) trips to the machine during its construction. He has a secret tunnel that he uses only for the return trips.
The farm comprises N (2 <= N <= 200) landmarks (numbered 1..N) connected by P (1 <= P <= 40,000) bidirectional trails (numbered 1..P) and with a positive length that does not exceed 1,000,000. Multiple trails might join a pair of landmarks.
To minimize his chances of detection, FJ knows he cannot use any trail on the farm more than once and that he should try to use the shortest trails.
Help FJ get from the barn (landmark 1) to the secret milking machine (landmark N) a total of T times. Find the minimum possible length of the longest single trail that he will have to use, subject to the constraint that he use no trail more than once. (Note well: The goal is to minimize the length of the longest trail, not the sum of the trail lengths.)
It is guaranteed that FJ can make all T trips without reusing a trail.
Input


* Line 1: Three space-separated integers: N, P, and T
* Lines 2..P+1: Line i+1 contains three space-separated integers, A_i, B_i, and L_i, indicating that a trail connects landmark A_i to landmark B_i with length L_i.
Output


* Line 1: A single integer that is the minimum possible length of the longest segment of Farmer John's route.
Sample Input

7 9 2
1 2 2
2 3 5
3 7 5
1 4 1
4 3 1
4 5 7
5 7 1
1 6 3
6 7 3
Sample Output

5
Hint


Farmer John can travel trails 1 - 2 - 3 - 7 and 1 - 6 - 7. None of the trails travelled exceeds 5 units in length. It is impossible for Farmer John to travel from 1 to 7 twice without using at least one trail of length 5.
Huge input data,scanf is recommended.
Source


USACO 2005 February Gold





题意：有N个地点，FJ 想从1走到N 每条边只能走一遍 走T次 求在满足条件下，最大的边最小。

题意有点绕，简而言之就是要你找出T条每条边都边不重复的路径，使得的这T条路径中的每段路径的最大值最小，求出这个最大值。首先找出T条边不重复的路径，可以想到用增光路来搞，把每条边的权值赋值为1，那整个网络的最大流就是边不重复的路径的数目了，因为每条边的流量为1，最多只能在一条增广路上，所以最终由多少个可行流就有多少条边不重复的路径，就是最大流了。那么这样就可以比较快的求出来。然后发现，给图的边加个限制，即权值小于等于limit的为可行边，那么T和limit是个线性关系，就可以二分来搞了。然后要注意这个题目的数据有平行边
思路：这题跟 poj 3228 Gold Transportation(二分+最大流) 这题差不多，就是用二分求出满足条件下的最小边权






#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int VM=210;
const int EM=500010;
const int INF=0x3f3f3f3f;
int N,P,T,cnt,head[VM],src,des;
int dep[VM];
struct Edge{
int from,to,nxt;
int cap;
}edge[EM],mat[EM];
void addedge(int cu,int cv,int cw){     //当是无向图时，反向边容量也是cap,有向边时，反向边容量是0
edge[cnt].to=cv;    edge[cnt].cap=cw;   edge[cnt].nxt=head[cu];
head[cu]=cnt++;
edge[cnt].to=cu;    edge[cnt].cap=cw;   edge[cnt].nxt=head[cv];
head[cv]=cnt++;
}
void buildgraph(int x){ //该题有重边，切忌用邻接矩阵删除重边(重边要用邻接表来处理以保留)
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=P;i++)   //源点向1连容量T的边。二分最小长度，长度超过mid的边容量为0，否则为1，用最大流判可行性
if(mat.cap<=x)
addedge(mat.from,mat.to,1);  //注意这里的流量为 1
}
int BFS(){
queue<int> q;
while(!q.empty())
q.pop();
memset(dep,-1,sizeof(dep));
dep[src]=0;
q.push(src);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head;i!=-1;i=edge.nxt){
int v=edge.to;
if(edge.cap>0 && dep[v]==-1){
dep[v]=dep+1;
q.push(v);
}
}
}
return dep[des]!=-1;
}
int DFS(int u,int minx){
if(u==des)
return minx;
int tmp;
for(int i=head;i!=-1;i=edge.nxt){
int v=edge.to;
if(edge.cap>0 && dep[v]==dep+1 && (tmp=DFS(v,min(minx,edge.cap)))){
edge.cap-=tmp;
edge[i^1].cap+=tmp;
return tmp;
}
}
dep=-1;
return 0;
}
int Dinic(){
int ans=0,tmp;
while(BFS()){
while(1){
tmp=DFS(src,INF);
if(tmp==0)
break;
ans+=tmp;
}
}
return ans;
}
int main(){
//freopen("input.txt","r",stdin);
while(~scanf("%d%d%d",&N,&P,&T)){
int l=INF,r=-INF;
for(int i=1;i<=P;i++){
scanf("%d%d%d",&mat.from,&mat.to,&mat.cap);
l=min(l,mat.cap);
r=max(r,mat.cap);
}
src=1,  des=N;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
buildgraph(mid);
int tmp=Dinic();
if(tmp>=T){     //注意这里
ans=mid;
r=mid-1;
}else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
　　SAP：
　　



#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int VM=210;
const int EM=300010;
const int INF=0x3f3f3f3f;
int N,P,T,cnt,head[VM],src,des;
int dep[VM],gap[VM],cur[VM],aug[VM],pre[VM];
struct Edge{
int frm,to,nxt;
int cap;
}edge[EM<<1],mat[EM<<1];
void addedge(int cu,int cv,int cw){     //无向图时反向边也为cw，有向图则为0
edge[cnt].to=cv;  edge[cnt].cap=cw;  edge[cnt].nxt=head[cu];
head[cu]=cnt++;
edge[cnt].to=cu;  edge[cnt].cap=cw;   edge[cnt].nxt=head[cv];
head[cv]=cnt++;
}
void buildgraph(int limit){
cnt=0;
memset(head,-1,sizeof(head));
for(int i=1;i<=P;i++)
if(mat.cap<=limit)
addedge(mat.frm,mat.to,1);
}
int SAP(int n){
int max_flow=0,u=src,v;
int id,mindep;
aug[src]=INF;
pre[src]=-1;
memset(dep,0,sizeof(dep));
memset(gap,0,sizeof(gap));
gap[0]=n;
for(int i=0;i<=n;i++)
cur=head; // 初始化当前弧为第一条弧
while(dep[src]<n){
int flag=0;
if(u==des){
max_flow+=aug[des];
for(v=pre[des];v!=-1;v=pre[v]){     // 路径回溯更新残留网络
id=cur[v];
edge[id].cap-=aug[des];
edge[id^1].cap+=aug[des];
aug[v]-=aug[des];   // 修改可增广量，以后会用到
if(edge[id].cap==0) // 不回退到源点，仅回退到容量为0的弧的弧尾
u=v;
}
}
for(int i=cur;i!=-1;i=edge.nxt){
v=edge.to;    // 从当前弧开始查找允许弧
if(edge.cap>0 && dep==dep[v]+1){  // 找到允许弧
flag=1;
pre[v]=u;
cur=i;
aug[v]=min(aug,edge.cap);
u=v;
break;
}
}
if(!flag){
if(--gap[dep]==0)    // gap优化，层次树出现断层则结束算法
break;
mindep=n;
cur=head;
for(int i=head;i!=-1;i=edge.nxt){
v=edge.to;
if(edge.cap>0 && dep[v]<mindep){
mindep=dep[v];
cur=i;   // 修改标号的同时修改当前弧
                }
}
dep=mindep+1;
gap[dep]++;
if(u!=src)  // 回溯继续寻找允许弧
u=pre;
}
}
return max_flow;
}
int main(){
//freopen("input.txt","r",stdin);
while(~scanf("%d%d%d",&N,&P,&T)){
int l=INF,r=-INF;
for(int i=1;i<=P;i++){
scanf("%d%d%d",&mat.frm,&mat.to,&mat.cap);
l=min(l,mat.cap);
r=max(r,mat.cap);
}
src=1,  des=N;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
buildgraph(mid);
int tmp=SAP(des+1);     //最大流表示能找出多少条符合的路径
if(tmp>=T){
ans=mid;
r=mid-1;
}else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
　　


下面这种SAP写法也挺不错的：






#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int VM=210;
const int EM=160010;     //建边重复1遍，所以是4*40000
int head[VM],oldhead[VM],dep[VM],gap[VM],cur[VM],pre[VM];
int cnt1,cnt;
int n,p,t,src,des;
struct Edge{
int to,cap,nxt;
}edge[EM],oldedge[EM];
void addedge1(int cu,int cv,int cw){
oldedge[cnt1].to=cv;
oldedge[cnt1].cap=cw;
oldedge[cnt1].nxt=oldhead[cu];
oldhead[cu]=cnt1++;
}
void addedge(int cu,int cv,int cw){
edge[cnt].to=cv;
edge[cnt].cap=cw;
edge[cnt].nxt=head[cu];
head[cu]=cnt++;
}
void build(int num){    //构建一新的图
memset(head,-1,sizeof(head));
cnt=0;
for(int u=1;u<=n;u++)
for(int i=oldhead;i!=-1;i=oldedge.nxt){
int v=oldedge.to;
if(oldedge.cap<=num){
addedge(u,v,1);  //边权为1就可以了
addedge(v,u,1);
}
}
}
int Sap(){
memset(dep,0,sizeof(dep));
memset(gap,0,sizeof(gap));
memcpy(cur,head,sizeof(head));
int u=pre[src]=src;
int res=0;
gap[0]=n;
while(dep[src]<n){
loop:
for(int &i=cur;i!=-1;i=edge.nxt){
int v=edge.to;
if(edge.cap && dep==dep[v]+1){
pre[v]=u;
u=v;
if(v==des){
res++;  //记录走了多少次
for(u=pre;v!=src;v=u,u=pre){
edge[cur].cap-=1;
edge[cur^1].cap+=1;
}
}
goto loop;
}
}
int mindep=n;
for(int i=head;i!=-1;i=edge.nxt){
int v=edge.to;
if(edge.cap && mindep>dep[v]){
cur=i;
mindep=dep[v];
}
}
if((--gap[dep])==0)
break;
dep=mindep+1;
gap[dep]++;
u=pre;
}
return res;
}
int main(){
//freopen("input.txt","r",stdin);
int u,v,w;
while(~scanf("%d%d%d",&n,&p,&t)){
memset(oldhead,-1,sizeof(oldhead));
cnt1=0;
src=1,des=n;
while(p--){
scanf("%d%d%d",&u,&v,&w);
addedge1(u,v,w);
addedge1(v,u,w);
}
int l=0,r=1000000;
int ans=0;
while(l<=r){
int mid=(l+r)>>1;
build(mid);
int sum=Sap();
sum/=2;  //这里要注意 因为建边是重复了，所以得除2 比如说：1到2有边 因为是无向图
if(sum>=t){ //当遍历到1结点时会建1-->2和2-->1，遍历到2时，会建2-->1和1-->2 所以重复
ans=mid;
r=mid-1;
}else
l=mid+1;
}
printf("%d\n",ans);
}
return 0;
}
View Code