博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu 5452 Minimum Cut 树形dp
阅读量:5750 次
发布时间:2019-06-18

本文共 2263 字,大约阅读时间需要 7 分钟。

Minimum Cut

Time Limit: 1 Sec  

Memory Limit: 256 MB

题目连接

http://acm.hdu.edu.cn/showproblem.php?pid=5452

Description

Given a simple unweighted graph G (an undirected graph containing no loops nor multiple edges) with n nodes and m edges. Let T be a spanning tree of G.

We say that a cut in G respects T if it cuts just one edges of T.

Since love needs good faith and hypocrisy return for only grief, you should find the minimum cut of graph G respecting the given spanning tree T.

Input

The input contains several test cases.

The first line of the input is a single integer t (1≤t≤5) which is the number of test cases.
Then t test cases follow.

Each test case contains several lines.

The first line contains two integers n (2≤n≤20000) and m (n−1≤m≤200000).
The following n−1 lines describe the spanning tree T and each of them contains two integers u and v corresponding to an edge.
Next m−n+1 lines describe the undirected graph G and each of them contains two integers u and v corresponding to an edge which is not in the spanning tree T.

Output

For each test case, you should output the minimum cut of graph G respecting the given spanning tree T.

Sample Input

1 4 5 1 2 2 3 3 4 1 3 1 4

Sample Output

Case #1: 2

HINT

 

题意

给你一个没有自环重边的无向图,然后给你一颗生成树,让你求一个最小割集的大小,使得这个割集有且只有一条边在这棵生成树上

题解:

树形dp,对于这个点,如果要消除他和他父亲之间的联系的话,代价就是他的子树所有连向外界的边就好了

跑一遍dfs维护一下就行了

-------------------------

我的方法是错的,已经被hack了

数据:

 2
4 4 1 2 2 3 3 4 1 3
4 4 1 3 2 3 2 4 1 2 

代码:

//qscqesze#include 
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
typedef long long ll;using namespace std;//freopen("D.in","r",stdin);//freopen("D.out","w",stdout);#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)#define maxn 20050#define mod 10007#define eps 1e-9int Num;char CH[20];//const int inf=0x7fffffff; //нчоч╢Сconst int inf=0x3f3f3f3f;//*********************************************************************************vector
Q[maxn];vector
E[maxn];int vis[maxn];int dp[maxn];int ans;void dfs(int x){ vis[x]=1; for(int i=0;i
y)swap(x,y); Q[x].push_back(y); } for(int i=n-1;i
y)swap(x,y); E[y].push_back(x); } dfs(1); printf("Case #%d: %d\n",cas,ans); }}

 

转载地址:http://bykkx.baihongyu.com/

你可能感兴趣的文章
数据结构与算法——常用排序算法及其Java实现
查看>>
你所不知的Webpack-多种配置方法
查看>>
webpack+typescript+threejs+vscode开发
查看>>
python读excel写入mysql小工具
查看>>
如何学习区块链
查看>>
搜索问题的办法
查看>>
微信分销系统商城营销5大重点
查看>>
求职准备 - 收藏集 - 掘金
查看>>
Linux-Centos启动流程
查看>>
php 设计模式
查看>>
后端技术精选 - 收藏集 - 掘金
查看>>
Laravel 服务容器
查看>>
mac安装kubernetes并运行echoserver
查看>>
多页架构的前后端分离方案(webpack+express)
查看>>
算法(第4版) Chapter 1
查看>>
前端技术选型的遗憾和经验教训
查看>>
“亲切照料”下的领域驱动设计
查看>>
SRE工程师到底是做什么的?
查看>>
解读:Red Hat为什么收购Ansible
查看>>
Ossim下的安全合规管理
查看>>