poj 3041( 最大匹配)

题意：给出一个矩阵和一些矩阵上的点，选择最少的行或列把给出的点覆盖。

思路：把行看成一个点集，列看成另一个点集，每个给出点构造一条这两个点集中的一条边。我们的问题就变成了选择最少的点把所有的边覆盖。很显然这就是一个最大独立点集问题，可用最大匹配求解。

匈牙利匹配算法：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define N 10010
#define M 20020
struct edge{
    int to,next;
}e[M];
int pre[N],visit[N],p[N];
int cnt;
void add(int a,int b)
{
    e[cnt].next=pre[a];
    e[cnt].to=b;
    pre[a]=cnt++;
}
bool dfs(int u)
{
    for(int edg=pre[u];edg!=0;edg=e[edg].next)
    {
        int v=e[edg].to;
        if(visit[v])continue;
        visit[v]=1;
        if(!p[v]||dfs(p[v]))
        {
            p[v]=u;
            return true;
        }
    }
    return false;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        cnt=1;
        int c=0;
        memset(p,0,sizeof(p));
        memset(pre,0,sizeof(pre));
        for(int i=1;i<=m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b+n);
            add(b+n,a);
        }

        for(int i=1;i<=n;i++)
        {
            memset(visit,0,sizeof(visit));
            if(dfs(i))c++;
        }
        printf("%d\n",c);
    }
    return 0;
}

最大流dinic算法（邻接矩阵实现）：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define inf 0x3f3f3f3f
#define N 1010
int S,T,L,R;
int flow[N][N],cap[N][N],level[N],q[N];
bool dinic_bfs()
{
    int rear=0,tail=1;
    q[0]=S;
    memset(level,0,sizeof(level));
    level[S]=1;
    while(rear<tail)
    {
        int u=q[rear++];
        for(int i=L;i<=R;i++)
        {
            if(!level[i]&&cap[u][i]-flow[u][i]>0)
            {
                level[i]=level[u]+1;
                q[tail++]=i;
            }
        }
    }
    return level[T]!=0;
}
int dinic_dfs(int u,int cp)
{
    int tmp=cp;
    if(u==T)return cp;
    for(int i=L;i<=R&&tmp;i++)
    {
        if(level[i]==level[u]+1&&cap[u][i]-flow[u][i]>0)
        {
            int t=dinic_dfs(i,min(tmp,cap[u][i]-flow[u][i]));
            flow[u][i]+=t;
            flow[i][u]-=t;
            tmp-=t;
        }
    }
    return cp-tmp;
}
int dinic()
{
    int tf=0,f;
    while(dinic_bfs())
    {
        while(f=dinic_dfs(S,inf))
        {
            tf+=f;
        }
    }
    return tf;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(flow,0,sizeof(flow));
        memset(cap,0,sizeof(cap));
        S=L=0;
        T=R=2*n+1;
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            cap[a][b+n]=1;
        }
        for(int i=1;i<=n;i++)
        {
            cap[S][i]=1;
            cap[i+n][T]=1;
        }
        printf("%d\n",dinic());
    }
    return 0;
}

最大流dinic算法（邻接表实现）：

#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
#define N 1010
#define M 20020
#define inf 0x3f3f3f3f
struct edge{
    int to,next,cap,flow;
}e[M];
int pre[N],level[N],q[N];
int cnt,S,T;
void add(int a,int b,int c)
{
    e[cnt].to=b;
    e[cnt].next=pre[a];
    e[cnt].cap=c;
    e[cnt].flow=0;
    pre[a]=cnt++;
}
bool dinic_bfs()
{
    int rear=0,tail=1;
    q[0]=S;
    memset(level,0,sizeof(level));
    level[S]=1;
    while(rear<tail)
    {
        int u=q[rear++];
        for(int edg=pre[u];edg!=0;edg=e[edg].next)
        {
            int v=e[edg].to;
            if(!level[v]&&e[edg].cap>e[edg].flow)
            {
                level[v]=level[u]+1;
                q[tail++]=v;
            }
        }
    }
    return level[T]!=0;
}
int dinic_dfs(int u,int cp)
{
    int tmp=cp;
    if(u==T)return cp;
    for(int edg=pre[u];tmp&&edg!=0;edg=e[edg].next)
    {
        int v=e[edg].to;
        if(level[v]==level[u]+1&&e[edg].cap>e[edg].flow)
        {
            int t=dinic_dfs(v,min(tmp,e[edg].cap-e[edg].flow));
            e[edg].flow+=t;
            e[edg^1].flow-=t;
            tmp-=t;
        }
    }
    return cp-tmp;
}
int dinic()
{
    int tf=0,f;
    while(dinic_bfs())
    {
        //cout<<1<<endl;
        while(f=dinic_dfs(S,inf))
        {
            //cout<<f<<endl;
            tf+=f;
        }
    }
    return tf;
}
int main()
{
    int n,m;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        memset(pre,0,sizeof(pre));
        int cnt=2;
        S=0;T=2*n+1;
        for(int i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            add(a,b+n,1);
            add(b+n,a,0);
        }
        for(int i=1;i<=n;i++)
        {
            add(S,i,1);
            add(i,S,0);
            add(i+n,T,1);
            add(T,i+n,0);
        }
        printf("%d\n",dinic());
    }
    return 0;
}