首页 > 代码库 > POJ2455 Secret Milking Machine【二分，最大流】
POJ2455 Secret Milking Machine【二分，最大流】
题目大意：N个点P条边，令存在T条从1到N的路径，求路径上的边权的最大值最小为多少
思路：做了好多二分+最大流的题了，思路很好出 二分出最大边权后建图，跑dinic
问题是。。。。这题是卡常数的好题！！！！！
T了8发以后实在受不了，瞄了眼网上的程序，齐刷刷的邻接矩阵。。。。论邻接矩阵的优越性
但不信邪的我终于反复优化常数后邻接表A了
//TLE的程序
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#define maxn 200090
#define esp 0.001
#define inf 0x3f3f3f3f
using namespace std;
int head[300],next[maxn],point[maxn],now=0;
int flow[maxn],dist[300];
int tt,p,h=0,n;
struct T
{
int x;int y;int v;
}a[maxn];
void add(int x,int y,int v)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
flow[now]=v;
next[++now]=head[y];
head[y]=now;
point[now]=x;
flow[now]=0;
}
int bfs(int s,int t,int x)
{
queue<int>q;
q.push(s);
memset(dist,-1,sizeof(dist));
dist[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=next[i])
{
int k=point[i];
if(flow[i]!=0&&dist[k]==-1)
{
dist[k]=dist[u]+1;
q.push(k);
}
}
}
return dist[t]!=-1;
}
int dfs(int s,int d,int t,int x)
{
if(s==t)return d;
int res=0;
for(int i=head[s];i&&res<d;i=next[i])
{
int u=point[i];
if(flow[i]&&dist[u]==dist[s]+1)
{
int dd=dfs(u,min(flow[i],d-res),t,x);
if(dd)
{
flow[i]-=dd;
flow[((i-1)^1)+1]+=dd;
res+=dd;
}
}
}
if(res==0)dist[s]=-1;
return res;
}
int judge(int x,int s,int t)
{
int ans=0;
memset(head,0,sizeof(head));
now=0;
for(int i=1;i<=p;i++)if(a[i].v<=x)
{
add(a[i].x,a[i].y,1);
add(a[i].y,a[i].x,1);
}
add(s,1,tt);add(n,t,inf);
while(bfs(s,t,x))
{ans+=dfs(s,inf,t,x);}
if(ans>=tt)return 1;else return 0;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
int main()
{
int x,y,v;
int l=0x3f3f3f3f,r=0,mid;
scanf("%d%d%d",&n,&p,&tt);
int s=n+10,t=n+12;
for(int i=1;i<=p;i++)
{
x=read();y=read();v=read();
a[i].x=x;a[i].y=y;a[i].v=v;
r=max(r,v);
l=min(l,v);
}
while(mid=(l+r)>>1,l<r)
{
if(judge(mid,s,t)==1)r=mid;else l=mid+1;
}
printf("%d\n",r);
return 0;
}
//AC的程序
#include <stdio.h>
#include <iostream>
#include <string.h>
#include <algorithm>
#include <queue>
#define maxn 200090
#define esp 0.001
#define inf 0x3f3f3f3f
using namespace std;
int head[300],next[maxn],point[maxn],now=0;
int flow[maxn],dist[300];
int tt,p,h=0,n;
struct T
{
int x;int y;int v;
}a[maxn];
void add(int x,int y,int v)
{
next[++now]=head[x];
head[x]=now;
point[now]=y;
flow[now]=v;
next[++now]=head[y];
head[y]=now;
point[now]=x;
flow[now]=0;
}
int bfs(int s,int t,int x)
{
queue<int>q;
q.push(s);
memset(dist,-1,sizeof(dist));
dist[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=next[i])
{
int k=point[i];
if(flow[i]!=0&&dist[k]==-1)
{
dist[k]=dist[u]+1;
q.push(k);
}
}
}
return dist[t]!=-1;
}
int dfs(int s,int d,int t,int x)
{
if(s==t)return d;
int res=0;
for(int i=head[s];i&&res<d;i=next[i])
{
int u=point[i];
if(flow[i]&&dist[u]==dist[s]+1)
{
int dd=dfs(u,min(flow[i],d-res),t,x);
if(dd)
{
flow[i]-=dd;
flow[((i-1)^1)+1]+=dd;
res+=dd;
}
}
}
if(res==0)dist[s]=-1;
return res;
}
int judge(int x,int s,int t)
{
int ans=0;
memset(head,0,sizeof(head));
now=0;
for(int i=1;i<=p;i++)if(a[i].v<=x)
{
add(a[i].x,a[i].y,1);
add(a[i].y,a[i].x,1);
}
add(s,1,tt);add(n,t,inf);
while(bfs(s,t,x))
{ans+=dfs(s,inf,t,x);}
if(ans>=tt)return 1;else return 0;
}
int read()
{
int x=0,f=1;char ch=getchar();
while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}
while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}
return x*f;
}
int main()
{
int x,y,v;
int l=0x3f3f3f3f,r=0,mid;
scanf("%d%d%d",&n,&p,&tt);
int s=n+10,t=n+12;
for(int i=1;i<=p;i++)
{
x=read();y=read();v=read();
a[i].x=x;a[i].y=y;a[i].v=v;
r=max(r,v);
l=min(l,v);
}
while(mid=(l+r)>>1,l<r)
{
if(judge(mid,s,t)==1)r=mid;else l=mid+1;
}
printf("%d\n",r);
return 0;
}
做完也是醉了，不A不睡觉TUT
POJ2455 Secret Milking Machine【二分，最大流】