看到题目，想了挺长时间，发现不会，然后看着样子像是树上成段操作，所以查了下树链刨分，结果真的就是这个东西。。。

Minimum Cut

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

Problem 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

Source

2015 ACM/ICPC Asia Regional Shenyang Online

#include <iostream>

#include <stdio.h>

#include <string.h>

#include <algorithm>

#include <math.h>

using namespace std;

#define N 20020

int n,m;

struct node

{

	int to,next;

}edge[2*N];

int pre[N],cnt;

int siz[N],son[N],top[N],dep[N],fa[N],w[N];

int index;

int cnt1[N];

void add_edge(int u,int v)

{

	edge[cnt].to=v;

	edge[cnt].next=pre[u];

	pre[u]=cnt++;

}

void dfs(int s,int deep,int father)

{

	dep[s]=deep;

	siz[s]=1;

	fa[s]=father;

	int mx=-1;

	son[s]=0;

	for(int p=pre[s];p!=-1;p=edge[p].next)

	{

		int v=edge[p].to;

		if(v==father) continue;

		dfs(v,deep+1,s);

		if(siz[v]>mx)

		{

			mx=siz[v];

			son[s]=v;

		}

		siz[s]+=siz[v];

	}

}

void dfs1(int s,int father)

{

	if(son[s]!=0)

	{

		w[ son[s] ]=++index;

		top[ son[s] ]=top[s];

		dfs1(son[s],s);

	}

	for(int p=pre[s];p!=-1;p=edge[p].next)

	{

		int v=edge[p].to;

		if(v==father||v==son[s]) continue;

		w[v]=++index;

		top[v]=v;

		dfs1(v,s);

	}

}

int Scan()     //输入外挂

{

	  int res=0,ch,flag=0;

	  if((ch=getchar())=='-')

		  flag=1;

	  else if(ch>='0'&&ch<='9')

		  res=ch-'0';

	  while((ch=getchar())>='0'&&ch<='9')

			res=res*10+ch-'0';

	  return flag?-res:res;

 }

void Out(int a)//输出外挂

{

	if(a>9)

		Out(a/10);

	putchar(a%10+'0');

}

int in()

{

    int flag = 1;

    char ch;

    int a = 0;

    while((ch = getchar()) == ' ' || ch == '\n');

    if(ch == '-') flag = -1;

    else

    a += ch - '0';

    while((ch = getchar()) != ' ' && ch != '\n')

    {

        a *= 10;

        a += ch - '0';

    }

    return flag * a;

}

//你卡这个复杂度真的好吗，不过也怪自己学的少。

int main()

{

	int T;

	scanf("%d",&T);

	int tt=1;

	while(T--)

	{

		memset(pre,-1,sizeof(pre));

		cnt=0;

		scanf("%d%d",&n,&m);

		for(int i=0;i<n-1;i++)

		{

			int x,y;

			scanf("%d%d",&x,&y);

			add_edge(x,y);

			add_edge(y,x);

		}

		//然后就是进行树链刨分

		dfs(1,1,1);

		top[1]=1;

		index=0;

		w[1]=0;

		dfs1(1,-1);

		memset(cnt1,0,sizeof(cnt1));

 		for(int i=n-1;i<m;i++)

		{

			int x,y;

			scanf("%d%d",&x,&y);

			while(top[x]!=top[y])

			{

				if( top[x] > top[y] )

				{

					cnt1[w[top[x]] ]++;

					cnt1[w[x]+1]--;

					x = fa[ top[x] ];

				}

				else

				{

					cnt1[ w[ top[y] ] ]++;

					cnt1[ w[y]+1 ]--;

					y = fa[ top[y] ];

				}

			}

			if(dep[x] < dep[y])

			{

				cnt1[ w[son[x] ] ]++;

				cnt1[ w[y]+1 ]--;

			}

			else if(dep[x] >dep[y] )

			{

				cnt1[w[son[y]] ]++;

				cnt1[w[x]+1 ]--;

			}

		}

		int ans=10000000;

		for(int i=1;i<=index;i++)

		{

			cnt1[i]+=cnt1[i-1];

			ans=min(ans,cnt1[i]);

		}

		printf("Case #%d: ",tt++);

		printf("%d\n",ans+1);

	}

    return 0;

}

巴特西

hdu 5452(树链刨分)

Minimum Cut

最新文章

热门文章