hdu 3225 Flowers Placement 二分图匹配+dfs

回来再写题解，上课去。。

#include <iostream>#include <cstdio>#include <algorithm>#define maxn 300005#define lson num<<1,s,mid#define rson num<<1|1,mid+1,e#include<cstdio>#include<cstring>#include<vector>using namespace std;#define N 205bool vis[N];vector<int> g[N];int maps[N];  //始终保存完备匹配的方案。int ans[205];int top,tot;int n,m,k;int use[205];int save[205];int find(int k,int st)  //找 从st+1——n是否能构成完备匹配{    if(k<=st) return 0;    for(int i=0;i<g[k].size();i++)    {        int boy=g[k][i];        if(!vis[boy])        {            vis[boy]=1;            if(maps[boy]==0||find(maps[boy],st))            {                maps[boy]=k;                return 1;            }        }    }    return 0;}bool isok(int now,int flo)   //假设now位置放flo花{    if(maps[flo]==now) return true;    int j;    for(int i=1;i<=n;i++)    {        save[i]=maps[i];        vis[i]=0;        if(maps[i]==now) j=i;   //找到上一次完备匹配now位置放的花    }    int t=maps[flo];                    //断开匹配    maps[flo]=now;    //修改匹配    maps[j]=0;    if(find(t,now)) return true;    //从now+1——n之间再次为t找一个匹配    else                            //没找到，则回溯    {        for(int i=1;i<=n;i++)            maps[i]=save[i];    }    return false;}bool dfs(int now){    if(now==n+1)    {        if(++tot==k) return true;        return false;    }    for(int i=0;i<g[now].size();i++)    {        int flo=g[now][i];        if(!use[flo]&&isok(now,flo))        {            use[flo]=1;            ans[now]=flo;            if(dfs(now+1)) return true;;            use[flo]=0;        }    }    return false;}int a[205][205];int main(){    int cas;    scanf("%d",&cas);    int x;    int ca=1;    while(cas--)    {        for(int i=0;i<=n;i++) g[i].clear();        memset(vis,0,sizeof(vis));        memset(a,0,sizeof(a));        memset(maps,0,sizeof(maps));        scanf("%d%d%d",&n,&m,&k);        for(int i=1;i<=m;i++)        {            for(int j=1;j<=n;j++)            {                scanf("%d",&x);                a[j][x]=1;            }        }        for(int i=1;i<=n;i++)        {            for(int j=1;j<=n;j++)            {                if(!a[i][j]) g[i].push_back(j);            }        }        int Ans=0;        for(int i=1;i<=n;i++)        {            memset(vis,0,sizeof(vis));            Ans+=find(i,-1);        }        if(Ans!=n)        {            printf("Case #%d: -1\n",ca++);            continue;        }        tot=0;        memset(use,0,sizeof(use));        if(dfs(1))        {            printf("Case #%d:",ca++);            for(int i=1;i<=n;i++)            {                printf(" %d",ans[i]);            }        }        else printf("Case #%d: -1",ca++);        puts("");    }    return 0;}