NBUT 1635 Explosion（最小顶点覆盖）

时间：2023-02-07 19:43:26

  • [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.
  • 样例输入
  • 2
    
5
    
1 2
    
2 3
    
3 4
    
4 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;

}

相关文章