0x6A 网络流初步

CH Round #17-C

这个算是一个技能点吧，不点不会，点了就没什么了。懒得写看书吧书上的1应该是0。。。

我又回来了太懒了不想翻书还是写写吧

必须边的判定条件：该边流量为0且两端的点在残余网络不在同一个联通分量

可行边的判定条件：该边流量为0或两端的点在残余网络在同一个联通分量

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int inf=(<<);

struct node

{

    int x,y,c,id,next,other;

}a[];int len,last[];

void ins(int x,int y,int c,int id)

{

    int k1,k2;

    len++;k1=len;

    a[len].x=x;a[len].y=y;a[len].c=c;a[len].id=id;

    a[len].next=last[x];last[x]=len;

    len++;k2=len;

    a[len].x=y;a[len].y=x;a[len].c=;a[len].id=-;

    a[len].next=last[y];last[y]=len;

    a[k1].other=k2;

    a[k2].other=k1;

}

int st,ed;

int h[],list[];

bool bt_h()

{

    int head=,tail=;list[]=st;

    memset(h,,sizeof(h));h[st]=;

    while(head!=tail)

    {

        int x=list[head];

        for(int k=last[x];k;k=a[k].next)

        {

            int y=a[k].y;

            if(h[y]==&&a[k].c>)

            {

                h[y]=h[x]+;

                list[tail++]=y;

            }

        }

        head++;

    }

    if(h[ed]==)return false;

    return true;

}

int findflow(int x,int f)

{

    if(x==ed)return f;

    int s=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(a[k].c>&&h[y]==h[x]+&&f>s)

        {

            int t=findflow(y,min(a[k].c,f-s));

            s+=t;a[k].c-=t;a[a[k].other].c+=t;

        }

    }

    if(s==)h[x]=;

    return s;

}

//------------------dicnic----------------------

bool b[];

struct enode

{

    int x,y,id,next;

}e[];int elen,elast[];

void eins(int x,int y,int id)

{

    elen++;

    e[elen].x=x;e[elen].y=y;e[elen].id=id;

    e[elen].next=elast[x];elast[x]=elen;

}

int z,dfn[],low[];

int top,sta[];bool v[];

int cnt,bel[];

void SCC(int x)

{

    dfn[x]=low[x]=++z;

    sta[++top]=x;v[x]=true;

    for(int k=elast[x];k;k=e[k].next)

    {

        int y=e[k].y;

        if(dfn[y]==)

        {

            SCC(y);

            low[x]=min(low[x],low[y]);

        }

        else if(v[y]==true)

            low[x]=min(low[x],dfn[y]);

    }

    if(dfn[x]==low[x])

    {

        int k;cnt++;

        do

        {

            k=sta[top];top--;

            v[k]=false;

            bel[k]=cnt;

        }while(k!=x);

    }

}

int aslen,as[];

int main()

{

    int n,m,T,x,y;

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

    st=n+m+,ed=n+m+;

    len=;memset(last,,sizeof(last));

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

        scanf("%d%d",&x,&y), ins(x,y+n,,i);

    for(int i=;i<=n;i++)ins(st,i,,-);

    for(int i=;i<=m;i++)ins(i+n,ed,,-);

    int ans=;

    while(bt_h())

    {

        ans+=findflow(st,inf);

    }

    //-----------------------------------------

    elen=;memset(elast,,sizeof(elast));

    memset(b,true,sizeof(b));

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

    {

        if(a[i].c==&&a[i].y>n&&a[i].x!=st&&a[i].y!=ed)b[a[i].id]=false;

        if(a[i].c==)

            eins(a[i].x,a[i].y,a[i].id);

    }

    z=,top=,cnt=;

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

        if(dfn[i]==)SCC(i);

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

        if(bel[e[i].x]==bel[e[i].y])b[e[i].id]=false;

    aslen=;

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

        if(b[i]==true)as[++aslen]=i;

    printf("%d\n",aslen);

    for(int i=;i<aslen;i++)printf("%d ",as[i]);

    if(aslen!=)printf("%d\n",as[aslen]);

    return ;

}

舞动的夜晚

poj1966 不难。拆点，删除一个点相当于把他的两个点之间的边割掉。有趣的是，这题枚举起始点和结束点，意在把这两个点分在不同的集合，使得图不联通。

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int inf=(<<);

struct node

{

    int x,y,c,next,other;

}a[],e[];int len,last[],elen,elast[];

void ins(int x,int y,int c)

{

    int k1,k2;

    len++;k1=len;

    a[len].x=x;a[len].y=y;a[len].c=c;

    a[len].next=last[x];last[x]=len;

    len++;k2=len;

    a[len].x=y;a[len].y=x;a[len].c=;

    a[len].next=last[y];last[y]=len;

    a[k1].other=k2;

    a[k2].other=k1;

}

int st,ed;

int h[],list[];

bool bt_h()

{

    int head=,tail=;list[]=st;

    memset(h,,sizeof(h));h[st]=;

    while(head!=tail)

    {

        int x=list[head];

        for(int k=last[x];k;k=a[k].next)

        {

            int y=a[k].y;

            if(h[y]==&&a[k].c>)

            {

                h[y]=h[x]+;

                list[tail++]=y;

            }

        }

        head++;

    }

    if(h[ed]==)return false;

    return true;

}

int findflow(int x,int f)

{

    if(x==ed)return f;

    int s=;

    for(int k=last[x];k;k=a[k].next)

    {

        int y=a[k].y;

        if(a[k].c>&&h[y]==h[x]+&&f>s)

        {

            int t=findflow(y,min(a[k].c,f-s));

            s+=t;a[k].c-=t;a[a[k].other].c+=t;

        }

    }

    if(s==)h[x]=;

    return s;

}

char ch;

void sc(int &x,int &y)

{

    ch=getchar();

    while(ch!='(')ch=getchar();

    scanf("%d",&x);x++;

    ch=getchar();

    while(ch!=',')ch=getchar();

    scanf("%d",&y);y++;

    ch=getchar();

    while(ch!=')')ch=getchar();

}

int main()

{

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        len=;memset(last,,sizeof(last));

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

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

        {

            int x,y;sc(x,y);

            ins(x+n,y,inf);ins(y+n,x,inf);

        }

        memcpy(e,a,sizeof(e));

        elen=len;memcpy(elast,last,sizeof(elast));

        int mmin=inf;

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

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

                if(i!=j)

                {

                    memcpy(a,e,sizeof(a));

                    len=elen;memcpy(last,elast,sizeof(last));

                    st=i+n,ed=j;

                    int ans=;

                    while(bt_h())

                    {

                        ans+=findflow(st,inf);

                    }

                    mmin=min(ans,mmin);

                }

        if(mmin==inf)printf("%d\n",n);

        else printf("%d\n",mmin);

    }

    return ;

}

poj1966

poj3422 算是套路题吧，拆点后对于一个点的自连，连一条流量为1，费用为点权的边，连一条流量为K-1，费用为0的边。开始我从1,1的出边为起始到n,n的入边，问题在于无法控制只跑K次。天真的我还写了while(K--&&spfa())事实证明这样错得一批

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

using namespace std;

const int inf=(<<);

struct node

{

    int x,y,c,d,next,other;

}a[];int len,last[];

void ins(int x,int y,int c,int d)

{

    int k1,k2;

    len++;k1=len;

    a[len].x=x;a[len].y=y;a[len].c=c;a[len].d=d;

    a[len].next=last[x];last[x]=len;

    len++;k2=len;

    a[len].x=y;a[len].y=x;a[len].c=;a[len].d=-d;

    a[len].next=last[y];last[y]=len;

    a[k1].other=k2;

    a[k2].other=k1;

}

int ans,st,ed;

int list[],d[],pre[],c[];

bool v[];

bool spfa()

{

    memset(d,,sizeof(d));d[st]=;

    memset(v,false,sizeof(v));v[st]=true;

    int head=,tail=;list[]=st;c[st]=inf;

    while(head!=tail)

    {

        int x=list[head];

        for(int k=last[x];k;k=a[k].next)

        {

            int y=a[k].y;

            if(a[k].c>&&d[y]>d[x]+a[k].d)

            {

                d[y]=d[x]+a[k].d;

                pre[y]=k;

                c[y]=min(a[k].c,c[x]);

                if(v[y]==false)

                {

                    v[y]=true;

                    list[tail++]=y;

                    if(tail==)tail=;

                }

            }

        }

        v[x]=false;

        head++;if(head==)head=;

    }

    if(d[ed]==d[])return false;

    else

    {

        ans+=d[ed]*c[ed];

        int y=ed;

        while(y!=st)

        {

            int k=pre[y];

            a[k].c-=c[ed];

            a[a[k].other].c+=c[ed];

            y=a[k].x;

        }

        return true;

    }

}

int n,mp[][];

int pt(int x,int y){return n*(x-)+y;}

int main()

{

    int K;

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

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

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

            scanf("%d",&mp[i][j]);

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

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

        {

            if(i!=n)ins(n*n+pt(i,j),pt(i+,j),K,);

            if(j!=n)ins(n*n+pt(i,j),pt(i,j+),K,);

            ins(pt(i,j),n*n+pt(i,j),,-mp[i][j]);

            ins(pt(i,j),n*n+pt(i,j),K-,);

        }

    st=pt(,);ed=n*n+pt(n,n);

    ans=;

    while(spfa()==true);

    printf("%d\n",-ans);

    return ;

}

poj3422

巴特西

0x6A 网络流初步

最新文章

热门文章