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