【BZOJ3651】网络通信

Description

有一个由M 条电缆连接的 N 个站点组成的网络。为了防止垄断，由 C 个公司控制所有的电缆，规定任何公司不能控制连接同一个站点的两条以上的电缆（可以控制两条）。同时规定，每个公司不能有多余的电缆，所谓的多余，是指属于同一个公司的电缆不能形成环。
在运作过程中，不同公司之间会进行电缆买卖。请你写一个程序判断买卖是否合法。

Input

输入第一行有4个由空格隔开的整数 N，M，C和 T。N(1≤N≤ 8 000)表示站点数，M(0≤M≤100 000)表示连接站点的电缆数。C(1≤C≤ 100)表表示公司数量，T 表示电缆买卖次
数。后面有M行，每行三个整数Sj1,Sj2和Kj，表示连接站点Sj1和Sj2(1≤Sj1< Sj2 ≤ n)的电缆属于Kj(1≤Kj≤C)公司拥有，任意两个站点只有一条直接相连的电缆，输入状态合法。最后T(0≤T≤100 000)行，每行三个整数 Si1, Si2和 Ki,表示 Ki公司想购买站点Si1和Si2之间的电缆。

Output

输出共 T行，表示处理的结果，有以下几种可能的结果：
1、“No such cable.” 两个站点间没有电缆。
2、 “Already owned.” 电缆己经是 Ki 公司控制。
3、 “Forbidden: monopoly.” Ki 公司己经控制了两条连接 Si1 或 Si2 的电缆。
4、 “Forbidden: redundant.” Ki 公司控制的线路会出现环。
5、 “Sold.” 可以买卖。

Sample Input

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

Sample Output

Sold.
Already owned.
Forbidden: monopoly.
Forbidden: redundant.
No such cable.

题解：LCT模板题。用map维护每条边属于哪个公司，然后将每个点拆成100个（对应属于每个公司的情况），剩下的LCT即可。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <map>

#include <utility>

#define MP(A,B) make_pair(A,B)

#define p(A,B) ((A-1)*n+B)

using namespace std;

const int maxn=100010;

typedef pair<int,int> pii;

struct LCT

{

	int ch[2],rev,fa;

}s[maxn<<3];

int n,m,C,T;

map<pii,int> mp;

int d[maxn<<3];

inline bool isr(int x){return s[s[x].fa].ch[0]!=x&&s[s[x].fa].ch[1]!=x;}

inline void pushdown(int x)

{

	if(s[x].rev)

	{

		swap(s[x].ch[0],s[x].ch[1]);

		if(s[x].ch[0])	s[s[x].ch[0]].rev^=1;

		if(s[x].ch[1])	s[s[x].ch[1]].rev^=1;

		s[x].rev=0;

	}

}

inline void rotate(int x)

{

	int y=s[x].fa,z=s[y].fa,d=(x==s[y].ch[1]);

	if(!isr(y))	s[z].ch[y==s[z].ch[1]]=x;

	s[x].fa=z,s[y].fa=x,s[y].ch[d]=s[x].ch[d^1];

	if(s[x].ch[d^1])	s[s[x].ch[d^1]].fa=y;

	s[x].ch[d^1]=y;

}

void updata(int x)

{

	if(!isr(x))	updata(s[x].fa);

	pushdown(x);

}

inline void splay(int x)

{

	updata(x);

	while(!isr(x))

	{

		int y=s[x].fa,z=s[y].fa;

		if(!isr(y))

		{

			if((x==s[y].ch[0])^(y==s[z].ch[0]))	rotate(x);

			else	rotate(y);

		}

		rotate(x);

	}

}

inline void access(int x)

{

	for(int y=0;x;splay(x),s[x].ch[1]=y,y=x,x=s[x].fa);

}

inline void maker(int x)

{

	access(x),splay(x),s[x].rev^=1;

}

inline void link(int x,int y)

{

	maker(x),s[x].fa=y;

}

inline void cut(int x,int y)

{

	maker(x),access(y),splay(y),s[y].ch[0]=s[x].fa=0;

}

inline int findr(int x)

{

	while(s[x].fa)	x=s[x].fa;

	return x;

}

inline int rd()

{

	int ret=0,f=1;	char gc=getchar();

	while(gc<'0'||gc>'9')	{if(gc=='-')f=-f;	gc=getchar();}

	while(gc>='0'&&gc<='9')	ret=ret*10+gc-'0',gc=getchar();

	return ret*f;

}

int main()

{

	n=rd(),m=rd(),C=rd(),T=rd();

	int i,a,b,c,e;

	for(i=1;i<=m;i++)

	{

		a=rd(),b=rd(),c=rd();

		if(a>b)	swap(a,b);

		mp[MP(a,b)]=c,link(p(c,a),p(c,b)),d[p(c,a)]++,d[p(c,b)]++;

	}

	for(i=1;i<=T;i++)

	{

		a=rd(),b=rd(),c=rd(),e=mp[MP(a,b)];

		if(a>b)	swap(a,b);

		if(!e)	puts("No such cable.");

		else	if(e==c)	puts("Already owned.");

		else	if(d[p(c,a)]>=2||d[p(c,b)]>=2)	puts("Forbidden: monopoly.");

		else	if(findr(p(c,a))==findr(p(c,b)))	puts("Forbidden: redundant.");

		else

		{

			puts("Sold.");

			mp[MP(a,b)]=c,cut(p(e,a),p(e,b)),link(p(c,a),p(c,b)),d[p(e,a)]--,d[p(e,b)]--,d[p(c,a)]++,d[p(c,b)]++;

		}

	}

	return 0;

}

Ki