題目就是讓求一個(gè)二分圖的最小點(diǎn)覆蓋，然后輸出字典序最小的方案。
依次從二分圖中刪除0..N-1中的一個(gè)點(diǎn)，如果此時(shí)最大匹配數(shù)減少了，就永久刪除這個(gè)點(diǎn)，然后輸出這個(gè)點(diǎn)，否則將該點(diǎn)恢復(fù)。
使用Hopcroft Karp算法157ms。
以下是我的代碼：
/*
* Author: lee1r
* Created Time: 2011/8/19 21:40:58
* File Name: poj3715.cpp
*/
#include<iostream>
#include<sstream>
#include<fstream>
#include<vector>
#include<list>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<bitset>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cctype>
#include<cmath>
#include<ctime>
#define L(x) ((x)<<1)
#define R(x) ((x)<<1|1)
#define Half(x) ((x)>>1)
#define Lowbit(x) ((x)&(-(x)))
using namespace std;
const int kInf(0x7f7f7f7f);
const double kEps(1e-8);
typedef unsigned int uint;
typedef long long int64;
typedef unsigned long long uint64;
const int kMaxn(207);
const int kMaxm(20007);
struct Edge
{
int u,v;
};
int N,M,r[kMaxn];
int cnt,first[kMaxn],next[kMaxm];Edge e[kMaxm];
int maxmatch,cx[kMaxn],cy[kMaxn];
int distx[kMaxn],disty[kMaxn];
int head,tail,q[kMaxn];
bool used[kMaxn];
void Clear()
{
cnt=0;
memset(first,-1,sizeof(first));
}
void AddEdge(int u,int v)
{
cnt++;
e[cnt].u=u;
e[cnt].v=v;
next[cnt]=first[u];
first[u]=cnt;
}
bool BFS()
{
bool re(false);
head=tail=0;
memset(distx,0,sizeof(distx));
memset(disty,0,sizeof(disty));
for(int i=0;i<N;i++)
if(used[i] && !r[i] && cx[i]==-1)
q[tail++]=i;
while(head!=tail)
{
int h,t;
for(h=head,t=tail;h!=t;h=(h+1)%kMaxn)
{
int u(q[h]);
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(!used[v])
continue;
if(!disty[v])
{
disty[v]=distx[u]+1;
if(cy[v]==-1)
re=true;
else
{
distx[cy[v]]=disty[v]+1;
q[tail]=cy[v];
tail=(tail+1)%kMaxn;
}
}
}
}
head=t;
}
return re;
}
bool DFS(int u)
{
for(int i=first[u];i!=-1;i=next[i])
{
int v(e[i].v);
if(!used[v])
continue;
if(disty[v]==distx[u]+1)
{
disty[v]=0;
if(cy[v]==-1 || DFS(cy[v]))
{
cx[u]=v;
cy[v]=u;
return true;
}
}
}
return false;
}
void HopcroftKarp()
{
maxmatch=0;
memset(cx,-1,sizeof(cx));
memset(cy,-1,sizeof(cy));
while(BFS())
for(int i=0;i<N;i++)
if(used[i] && !r[i] && cx[i]==-1 && DFS(i))
maxmatch++;
}
int main()
{
#ifndef ONLINE_JUDGE
//freopen("data.in","r",stdin);
#endif
int T;
scanf("%d",&T);
while(T--)
{
Clear();
scanf("%d%d",&N,&M);
for(int i=0;i<N;i++)
scanf("%d",&r[i]);
while(M--)
{
int u,v;
scanf("%d%d",&u,&v);
if(r[u]!=r[v])
{
if(r[u]==0)
AddEdge(u,v);
else
AddEdge(v,u);
}
}
for(int i=0;i<N;i++)
used[i]=true;
HopcroftKarp();
int ans(maxmatch);
printf("%d",ans);
for(int i=0;i<N && ans;i++)
{
used[i]=false;
HopcroftKarp();
if(maxmatch<ans)
printf(" %d",i);
else
used[i]=true;
ans=maxmatch;
}
printf("\n");
}
return 0;
}
posted on 2011-08-19 22:07
lee1r 閱讀(396)
評(píng)論(0) 編輯 收藏 引用 所屬分類(lèi):
題目分類(lèi)：圖論