POJ1325

题目大意：

有两台机器\(A,B\),分别有\(n,m\)种不同模式，有\(k\)个任务，第\(i\)个任务在\(A\)上需要模式\(a_i\)，在\(B\)上需要模式\(b_i\)，要完成两台机器最少转化多少次模式？

贪心地考虑如果我们决定在某一时刻把机器\(A\)调为\(a_i\)，那么一定把所有在\(A\)上需要模式\(a_i\)的任务都解决掉是最优的

如果我们把\(A,B\)的每个模式看作一个节点，每个任务看作连接\(a_i,b_i\)的一条边，那么任意一个节点可以覆盖所有与之相连的边

我们的任务是需要最少的节点覆盖所有的边

所以是裸的二分图最小点覆盖

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
namespace red{
#define int long long
#define eps (1e-8)
    inline int read()
    {
        int x=0;char ch,f=1;
        for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());
        if(ch=='-') f=0,ch=getchar();
        while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}
        return f?x:-x;
    }
    const int N=1e4+10;
    int n,m,k;
    struct node
    {
        int id,x,y;
    }d[N];
    int f[N],ret;
    bool vis[N];
    int head[N],cnt;
    struct point
    {
        int nxt,to;
        point(){}
        point(const int &nxt,const int &to):nxt(nxt),to(to){}
    }a[N<<2];
    inline void link(int x,int y)
    {
        a[++cnt]=point(head[x],y);head[x]=cnt;
        a[++cnt]=point(head[y],x);head[y]=cnt;
    }
    inline bool find(int x)
    {
        for(int i=head[x];i;i=a[i].nxt)
        {
            int t=a[i].to;
            if(vis[t]) continue;
            vis[t]=1;
            if(!f[t]||find(f[t]))
            {
                f[t]=x;
                return 1;
            }
        }
        return 0;
    }
    inline void main()
    {
        while("haku")
        {
            n=read();
            if(!n) break;
            m=read(),k=read();
            memset(head,0,sizeof(head));
            memset(f,0,sizeof(f));
            cnt=ret=0;
            for(int i=1;i<=k;++i)
            {
                d[i].id=read(),d[i].x=read(),d[i].y=read();
                if(!d[i].x||!d[i].y) continue;
                link(d[i].x,d[i].y+n);
            }
            for(int i=1;i<=n;++i)
            {
                memset(vis,0,sizeof(vis));
                if(find(i)) ++ret;
            }
            printf("%lld\n",ret);
        }
    }
}
signed main()
{
    red::main();
return 0;
}

POJ1325

原文：https://www.cnblogs.com/knife-rose/p/12085275.html