loj 1201(最大独立集)

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=26913

思路:水题一枚,就是求最大独立集。最大独立集=顶点数-最大匹配。

 #include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
#define MAXN 1111
#define FILL(a,b) memset(a,b,sizeof(a)) int n,m,ly[MAXN];
bool mark[MAXN]; vector<int>g[MAXN]; int dfs(int u)
{
for(int i=;i<g[u].size();i++){
int v=g[u][i];
if(!mark[v]){
mark[v]=true;
if(ly[v]==-||dfs(ly[v])){
ly[v]=u;
return ;
}
}
}
return ;
} int MaxMatch()
{
int res=;
FILL(ly,-);
for(int i=;i<=n;i++){
FILL(mark,false);
res+=dfs(i);
}
return res/;
} int main()
{
int _case,u,v,t=;
scanf("%d",&_case);
while(_case--){
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++)g[i].clear();
while(m--){
scanf("%d%d",&u,&v);
g[u].push_back(v);
g[v].push_back(u);
}
printf("Case %d: %d\n",t++,n-MaxMatch());
}
return ;
}
上一篇:NancyFX 第三章 Web框架


下一篇:转)MySQL日期与时间函数