[1635] Explosion
时间限制: 10000 ms内存限制: 65535 K问题描述there is a country which containsncities connected byn - 1roads(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;}
