首页 > 代码库 > NBUT 1635 Explosion（最小顶点覆盖）

NBUT 1635 Explosion（最小顶点覆盖）

2024-08-11 02:47:02   217人阅读

  • [1635] Explosion

  • 时间限制: 10000 ms　内存限制: 65535 K
  • 问题描述

  • there is a country which contains n cities connected by n - 1 roads(just like a tree). If you place TNT in one city, all the roads connect these city will be destroyed, now i want to destroy all the roads with the least number of TNT, can you help me ?

  • 输入
  • Input starts with an integer T(T <= 500), denoting the number of test case.
    For each test case, first line contains n(1 <= n <= 1000), denoting the number of cities, next n - 1lines following and each line contains two different cities denoting these two cities connect directly. You can assume the input guarantee the relation among cities is a tree.
  • 输出
  • For each test case, print the least number of TNT that i need to destroy all the n - 1 roads.
  • 样例输入 
  • 251 22 33 44 5
  • 样例输出
  • 2

 

题目链接：NBUT 1635

又是一道没人写的水题……由于题目中说like a tree，因此可以归为二分图，然后就套公式，在二分图中最小顶点覆盖数=最大匹配数。（另外这题应该是可以用树形DP做然而并不会……以后再说- -|||）

代码：

#include<iostream>#include<algorithm>#include<cstdlib>#include<sstream>#include<cstring>#include<bitset>#include<cstdio>#include<string>#include<deque>#include<stack>#include<cmath>#include<queue>#include<set>#include<map>using namespace std;#define INF 0x3f3f3f3f#define CLR(x,y) memset(x,y,sizeof(x))#define LC(x) (x<<1)#define RC(x) ((x<<1)+1)#define MID(x,y) ((x+y)>>1)typedef pair<int,int> pii;typedef long long LL;const double PI=acos(-1.0);const int N=1010;struct edge{	int to;	int pre;};edge E[N<<1];int head[N],ne;int vis[N],match[N];void add(int s,int t){	E[ne].to=t;	E[ne].pre=head[s];	head[s]=ne++;}void init(){	CLR(head,-1);	ne=0;	CLR(match,-1);}int dfs(int now){	for (int i=head[now]; ~i; i=E[i].pre)	{		int v=E[i].to;		if(!vis[v])		{			vis[v]=1;			if(match[v]==-1||dfs(match[v]))			{				match[v]=now;				return 1;			}		}	}	return 0;}int hun(int n){	int r=0;	for (int i=1; i<=n; ++i)	{		CLR(vis,0);		if(dfs(i))			++r;	}	return r;}int main(void){	int tcase,n,a,b,i,j,ans;	scanf("%d",&tcase);	while (tcase--)	{		init();		scanf("%d",&n);		for (i=0; i<n-1; ++i)		{			scanf("%d%d",&a,&b);			add(a,b);			add(b,a);		}		printf("%d\n",hun(n)>>1);	}	return 0;}

NBUT 1635 Explosion（最小顶点覆盖）


联系
我们