poj3692 最大点权独立集/最大独立集

题意:有男孩和女孩，男孩之间全部认识，女孩之间全部认识，一部分男孩和女孩认识，现在希望选出一些孩子，这些孩子都相互认识。

方法:正的做不好做，观察他的补图，补图之间无关系的边就是原图有关系的。补图中的独立集不正是相互都没有连边么，反过来说，它们在原图中不正是两两都有连边么。

最小割：

#include<stdio.h>

#include<string.h>

#include<queue>

#define INF 99999999

using namespace std;

const int maxn = ;

struct node

{

    int to;

    int v;

    int flag;

    int next;

}edge[*];

int pre[maxn],index,vis[maxn],S,T,map[maxn][maxn];

void add(int x,int y,int z)

{

    edge[index].to=y;

    edge[index].v=z;

    edge[index].flag=index+;

    edge[index].next=pre[x];

    pre[x]=index++;

    edge[index].to=x;

    edge[index].v=;

    edge[index].flag=index-;

    edge[index].next=pre[y];

    pre[y]=index++;

}

int dfs(int u,int low)

{

    int i,used=;

    if(u==T)

        return low;

    for(i=pre[u];i!=-&&used<low;i=edge[i].next)

    {

        if(vis[edge[i].to]==vis[u]+&&edge[i].v)

        {

            int a=dfs(edge[i].to,min(low-used,edge[i].v));

            edge[i].v-=a;

            edge[edge[i].flag].v+=a;

            used+=a;

        }

    }

    if(!used)

        vis[u]=-;

    return used;

}

int BFS()

{

    int i;

    queue<int>q;

    memset(vis,-,sizeof(vis));

    vis[]=;

    q.push();

    while(!q.empty())

    {

        int t=q.front();

        q.pop();

        for(i=pre[t];i!=-;i=edge[i].next)

        {

            if(vis[edge[i].to]<&&edge[i].v)

            {

                vis[edge[i].to]=vis[t]+;

                q.push(edge[i].to);

            }

        }

    }

    if(vis[T]>)

        return ;

    return ;

}

int main()

{

    int i,j,n,m,k,ft=;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        if(!n&&!m&&!k)

            break;

        memset(map,,sizeof(map));

        memset(pre,-,sizeof(pre));

        index=;

        S=,T=n+m+;

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

        {

            add(,i,);

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

            {

                if(i==j)continue;

                map[i][j]=;

            }

        }

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

        {

            add(i+n,T,);

            for(j=;j<=m;j++)

            {

                if(i==j)continue;

                map[i+n][j+n]=;

            }

        }

        for(i=;i<k;i++)

        {

            int x,y;

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

            map[x][y+n]=;

        }

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

        {

            for(j=;j<=m;j++)

            {

                if(!map[i][j+n])

                    add(i,j+n,INF);

            }

        }

        int ans=;

        while(BFS())

        {

            while()

            {

                int a=dfs(,INF);

                if(!a)break;

                ans+=a;

            }

            //printf("1");

        }

        printf("Case %d: %d\n",++ft,n+m-ans);

    }

}

二分匹配:

#include<stdio.h>

#include<string.h>

#include<queue>

#define INF 99999999

using namespace std;

const int maxn = ;

int match[maxn],vis[maxn],map[maxn][maxn];

int dfs(int u,int m)

{

    int i,j;

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

    {

        if(!vis[i]&&!map[u][i])

        {

            vis[i]=;

            if(match[i]==-||dfs(match[i],m))

            {

                match[i]=u;

                return ;

            }

        }

    }

    return ;

}

int main()

{

    int i,j,n,m,k,ft=;

    while(~scanf("%d%d%d",&n,&m,&k))

    {

        if(!n&&!m&&!k)

            break;

        memset(match,-,sizeof(match));

        memset(map,,sizeof(map));

        for(i=;i<k;i++)

        {

            int x,y;

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

            map[x][y]=;

        }

        int ans=;

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

        {

            memset(vis,,sizeof(vis));

            if(dfs(i,m))

               ans++;

        }

        printf("Case %d: %d\n",++ft,n+m-ans);

    }

}