首页 > 程序开发 > 软件开发 > 其他 >

HDU 5452 Minimum Cut 2015沈阳网络赛(在线LCA)

2016-09-16

Minimum Cut Time Limit: 3000 2000 MS (Java Others)Memory Limit: 65535 102400 K (Java Others) Total Submission(s): 1514Accepted Submission(s): 715 Problem Description Given a simp

Minimum Cut

Time Limit: 3000/2000 MS (Java/Others)Memory Limit: 65535/102400 K (Java/Others)
Total Submission(s): 1514Accepted Submission(s): 715


Problem Description Given a simple unweighted graphG\ (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 graphG\ 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 graphG\ 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

Source 2015 ACM/ICPC Asia Regional Shenyang Online
Recommend wange2014|We have carefully selected several similar problems for you:58715870586858675866 题意:给你一个图G,让你求删除最少多少的边可以使的图G变为不连通,且所删除的边有且仅有一条属于图G的生成树T。即问你图的最小割集是多大?
题解:因为考虑生成树中的每一个结点,将其子树与其父节点分离需要去掉其父边以及其子树中的结点与其他子树相连的边,其父边就是生成树中的边,与其他子树相连的边为非生成树中的边。这样只需统计每一个子树关联的非生成树中的边数,取最小值,然后+1就是答案。
对于每一个结点i,设num[ i ]为结点 i 的子树关联的非生成树中的边数,或者说,num存的是删除某个结点 i 需要删除的边的数量。则num[ i ] = sum( num [ k ] ) k为i的子节点。对于非生成树中的边的两个结点u,v,不难发现,除了LCA(u,v),u到LCA(u,v)以及v到LCA(u,v)所经过的所有节点的num[ i ]都增加了1,因此当处理每一条非生成树中的边的两个顶点u,v,num[ u ] ++,num[ v ] ++,num[LCA(u,v)] - = 2,然后DFS,回溯时自底向上更新一边num[ i ]的值即可。
AC代码:
#pragma comment(linker, "/STACK:102400000,102400000")
//#include
#include 
#include 
#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include  
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair pii;
typedef vector vi;
const double eps = 1e-8;  
const int INF = 0x3f3f3f3f; 
const ll inf =(1LL<<62) ;
const int MOD = 1e9 + 7;  
const ll mod = (1LL<<32);
const int N =8e4+7; 
const int M=100010;
const int maxn=1001;
#define mst(a) memset(a, 0, sizeof(a))
#define M_P(x,y) make_pair(x,y)
#define pi acos(-1.0)
#define in freopen("in.txt","r",stdin) 
#define rep(i,j,k) for (int i = j; i <= k; i++)  
#define per(i,j,k) for (int i = j; i >= k; i--)  
#define lson x << 1, l, mid  
#define rson x << 1 | 1, mid + 1, r  
const int lowbit(int x) { return x&-x; }
//const int lowbit(int x) { return ((x)&((x)^((x)-1))); } 
int read(){ int v = 0, f = 1;char c =getchar();
while( c < 48 || 57 < c ){if(c==&#39;-&#39;) f = -1;c = getchar();}
while(48 <= c && c <= 57) v = v*10+c-48, c = getchar();
return v*f;}
int dp[2*N][26];  //数组开到2*N,因为遍历后序列长度为2*n-1
bool vis[26];
struct edge
{
    int from, to;
    int next;
} e[2*N];
int tot,head[N];
int cnt;
int num[N];
void init()
{
    memset(head,-1,sizeof(head));
    memset(vis,false,sizeof(vis));
    memset(num,0,sizeof(num));
    cnt = 0;
}
void addedge(int u, int v)
{
    e[cnt].from = u;
    e[cnt].to = v;
    e[cnt].next = head[u];
    head[u] = cnt++;
}
int ver[2*N], R[2*N], first[N];
//ver:节点编号  R:深度   first:点编号位置
void dfs(int u ,int dep)
{
    vis[u] = true;
    ver[++tot] = u;
    first[u] = tot;
    R[tot] = dep;
    for(int k=head[u]; k!=-1; k=e[k].next)
        if( !vis[e[k].to] )
        {
            int v = e[k].to;
            dfs(v, dep+1);
            ver[++tot] = u;
            R[tot] = dep;
        }
}
void ST(int n)
{
    for(int i=1; i<=n; i++)
        dp[i][0] = i;
    for(int j=1; (1< y) swap(x,y);
    int res = RMQ(x,y);
    return ver[res];
}

int DFS(int u,int fa)
{
    for(int i = head[u]; ~i; i = e[i].next)
    {
        int v = e[i].to;
        if(v == fa)
            continue;
        DFS(v, u);
        num[u]+=num[v];
    }
    return 0;
}

int main()
{
    int t;
    int cas = 0;
    int n, m;
    scanf("%d",&t);
    while(t--)
    {
        init();
        scanf("%d%d",&n,&m);
        int u, v;
        for(int i = 0; i < n-1; i++)
        {
            scanf("%d%d",&u,&v);
            addedge(u, v);
            addedge(v, u);
        }
        for(int i = n; i <= m; i++)
        {
            scanf("%d%d",&u,&v);
            int tt = LCA(u, v);
            num[u]++;
            num[v]++;
            num[tt]-=2;//一条边两个端点 贡献为2
        }
        DFS(1, 1);
        int ans = INF;
        for(int i = 2; i <= n; i++)
        {
            ans = min(ans, num[i]+1);
        }
        printf("Case #%d: %d\n",++cas,ans);
    }
    return 0;
}
/*
1
6 7
1 2
2 3
3 4
4 5
5 6
6 7
1 3
4 6
输出应该是:1 。。。 
*/

题目数据应该很弱!
相关文章
最新文章
热点推荐