hdu3572

题解：

网络流

判断是否为漫流

代码:

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <cstdlib>

using namespace std;

const int INF=1e9,N=,M=,FIN=;

typedef long long ll;

int n,m,s,t,sum,ec,head[N],first[N],que[N],lev[N],Next[M],to[M],v[M];

void init()

{

    sum=ec=;

    memset(first,-,sizeof(first));

    s=,t=FIN;

}

void addEdge(int a,int b,int c)

{

    to[ec]=b;

    v[ec]=c;

    Next[ec]=first[a];

    first[a]=ec++;

    to[ec]=a;

    v[ec]=;

    Next[ec]=first[b];

    first[b]=ec++;

}

int BFS()

{

    int kid,now,f=,r=;

    memset(lev,,sizeof(lev));

    que[]=s,lev[s]=;

    while (f<r)

     {

        now=que[f++];

        for (int i=first[now];i!=-;i=Next[i])

         {

            kid=to[i];

            if (!lev[kid]&&v[i])

             {

                lev[kid]=lev[now]+;

                if (kid==t)return ;

                que[r++]=kid;

             }

         }

     }

    return ;

}

int DFS(int now, int sum)

{

    int kid,flow,rt=;

    if (now==t) return sum;

    for (int i=head[now];i!=-&&rt<sum;i=Next[i])

     {

        head[now]=i;

        kid=to[i];

        if (lev[kid]==lev[now]+&&v[i])

         {

            flow=DFS(kid,min(sum-rt,v[i]));

            if (flow)

             {

                v[i]-=flow;

                v[i^]+=flow;

                rt+=flow;

             }

            else lev[kid]=-;

         }

     }

    return rt;

}

int dinic()

{

    int ans=;

    while (BFS())

     {

        for (int i=;i<=t;i++)head[i]=first[i];

        ans+=DFS(s,INF);

     }

    return ans;

}

void input()

{

    int Min=INF,Max=;

    scanf("%d%d",&n,&m);

    int a,b,c;

    for (int i=;i<=n;i++)

     {

        scanf("%d%d%d",&a,&b,&c);

        sum+=a;

        addEdge(s,i,a);

        for (int j=b;j<=c;j++)addEdge(i,j+n,);

        if (c<b)swap(c,b);

        if (Min>b)Min=b;

        if (Max<c)Max=c;

     }

    for (int i=Min;i<=Max;i++)addEdge(i+n,t,m);

}

int main()

{

    int T,Case=;

    scanf("%d",&T);

    while (T--)

     {

        printf("Case %d: ",Case++);

        init();

        input();

        if (dinic()==sum) puts("Yes");

        else puts("No");

        puts("");

     }

    return ;

}