SPOJ UOFTCG - Office Mates (树的最小路径覆盖)
UOFTCG - Office Mates
Dr. Baws has an interesting problem. His N
graduate students, while friendly with some select people, are
generally not friendly with each other. No graduate student is willing
to sit beside a person they aren't friends with.
The desks are up against the wall, in a single line, so it's possible
that Dr. Baws will have to leave some desks empty. He does know which
students are friends, and fortunately the list is not so long: it turns
out that for any subset of K
graduate students, there are at most K−1
pairs of friends. Dr. Baws would like you to minimize the total number of desks required. What is this minimum number?
Input
The input begins with an integer T≤50
, the number of test cases. Each test case begins with two integers on their own line: N≤100000, the number of graduate students (who are indexed by the integers 1 through N), and M, the number of friendships among the students. Following this are M lines, each containing two integers i and j separated by a single space. Two integers i and j represent a mutual friendship between students i and j
.
The total size of the input file does not exceed 2 MB.
Output
For each test case output a single number: the minimum number of desks Dr. Baws requires to seat the students.
Example
Input:
1
6 5
1 2
1 3
1 4
4 5
4 6
Output:
7
Explanation of Sample:
As seen in the diagram, you seat the students in two groups of three with one empty desk in the middle.
【分析】有一群人,有的人互为朋友,现在有一排椅子,将这些人安排在椅子上,要求不是朋友的两个人不能坐在一起,即可以将他俩隔开或者中间放个空的椅子。
已知K个人最多有K-1对朋友。问最少需要多少椅子。
树的最小路径覆盖模板题。
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <string>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define inf 0x3f3f3f3f
#define met(a,b) memset(a,b,sizeof a)
#define pb push_back
typedef long long ll;
using namespace std;
const int N = ;
const int M = ;
const int mod=1e9+;
int n,m;
int T,cnt;
int head[N],ans[N],vis[N];
bool mark[N];
struct edge{int to,next;}edg[N*];
void add(int u,int v)
{
edg[++cnt].to=v;edg[cnt].next=head[u];head[u]=cnt;
edg[++cnt].to=u;edg[cnt].next=head[v];head[v]=cnt;
}
void dfs(int x,int f)
{
ans[x]=vis[x]=;
int tot=;
for(int i=head[x];i!=-;i=edg[i].next)
{
if(edg[i].to==f)continue;
dfs(edg[i].to,x);
ans[x]+=ans[edg[i].to];
if(!mark[edg[i].to])tot++;
}
if(tot>=)ans[x]-=,mark[x]=;
else if(tot==)ans[x]--;
}
int main()
{
int u,v;
scanf("%d",&T);
while(T--)
{
cnt=;
met(head,-);
met(ans,);
met(mark,);
met(vis,);
scanf("%d%d",&n,&m);
while(m--)
{
scanf("%d%d",&u,&v);
add(u,v);
}
int anss=,ret=;;
for(int i=;i<=n;i++){
if(!vis[i]){
ret++;
dfs(i,);
vis[i]=;
anss+=ans[i]-;
}
}
printf("%d\n",anss+ret-+n);
}
return ;
}
最新文章
- ArrayList实现删除重复元素(元素不是对象类型的情况)
- VS2010的项目配置
- C#实现WebService服务 项目完整总结
- DevPress GridControl添加按钮列
- 怎样手动添加 Sublime 3 右键菜单
- Bata版本冲刺计划及安排
- c语言趣味
- Codeforces Round #360 div2
- 轻松学习RSA加密算法原理 (转)
- poj2932 Coneology (扫描线)
- ASPNETPager常用属性
- ZA7783:MIPI转LVDS/MIPI转RGB888/RGB转LVDS
- String... args 和 String[] args 的区别
- Eclipse项目中web app libraries和 Referenced Libraries区别
- javascript 把时间戳转为时间 ajax HTML拼装
- Mac超快速搭建Nginx、PHP、PHPStorm、XDebug环境
- poj2823 单调队列初步
- 《团队-爬取豆瓣电影TOP250-设计文档》
- UI基础:UIScrollView、UIPageControl
- ios 给图片加文字