【BZOJ-3651&3081】网络通信&StrangeRegulations Link-Cut-Tree

3651: 网络通信

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 90 Solved: 61
[Submit][Status][Discuss]

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.

HINT

Source

3081: [Cerc2011]Strange Regulations

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 37 Solved: 14
[Submit][Status][Discuss]

Description

在一个计算机网络中，连接两台计算机的电缆属于不同的公司。一项新的反垄断法规定，一家公司连接同一台计算机的电缆不能超过两条。为了避免资源浪费，另外一条法律规定，一家公司的电缆系统不能有冗余，即去掉任意一个电缆之后，至少一对之前连通的计算机要断开连接。由于这些公司不断的销售和购入电缆，要确定他们是否遵守这些规则十分的困难。你的任务是写一个程序完成这个任务

Input

多组测试数据。第一行是4个整数N，M，C，T——计算机的数量1<=N=8000，电缆的数量0<=M<=100000，公司的数量1<=C<=100，电缆销售/购入的数量0<=T<=100000。

接下来M行，每行三个整数Sj1,Sj2,Kj，代表这条电缆连接的两个服务器Sj1,Sj2以及电缆所属的公司Kj。初始状态是遵守规则的。

接下来行，每行3个整数Si1,Si2,Ki，表示公司购入了连接S1,S2的电缆。

4个0标志着测试文件的结束。

Output

对于每个测试数据，输出行：

“No Such Cable.” 如果这对服务器之前没有被一对电缆相连

“Already owned.” 如果这对电缆本来就属于这家公司

“Frobidden: monopoly.” 如果公司Ki已经有2条电缆与S1或S2相连

“Forbidden: redundant.” 如果公司Ki公司购入这条电缆后，会在其网络中形成环

“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
2 1 1 1
1 2 1
1 2 1
0 0 0 0

Sample Output

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

Already owned.

HINT

Source

Solution

P3651：

裸LCT，多了一点点处理，我们近似把题意理解为染色

首先用map记录每个边的颜色情况，再用一个数组记录每个点的每种颜色的度，最后每个颜色开一个n个点的LCT维护即可

那么讨论一下即可：

利用map里的信息可以得到Already owned.或No such cable.

利用记录度的数组可以得到Forbidden: monopoly.

设更改前的颜色为c1，更改后的为c2，如果c2中两点在同一个联通块中，则为Forbidden: redundant.

否则为Sold.并cut掉c1中的，link起来c2中的即可

要注意的是，把LCT写到struct里，要用构造函数进行初始化！

P3081：

3651原题，多组数据，注意每次处理即可

Code

p3651

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<map>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define N 8010
int n,m,c,t; int colout[N][110];
map<int,int>color[N];
struct LCTnode{
int fa[N],son[N][2],s[N],val[N],size[N];bool rev[N];
LCTnode(){memset(fa,0,sizeof(fa));memset(son,0,sizeof(son));memset(s,0,sizeof(s));
memset(val,0,sizeof(val));memset(size,0,sizeof(size));memset(rev,0,sizeof(rev));}
inline bool is_root(int x){return !fa[x]||son[fa[x]][1]!=x&& son[fa[x]][0]!=x;}
inline void rev1(int x){if (!x)return; swap(son[x][0],son[x][1]);rev[x]^=1;}
void pb(int x){if (rev[x]) rev1(son[x][0]),rev1(son[x][1]),rev[x]=0;}
inline void update(int x){size[x]=size[son[x][0]]+1+size[son[x][1]];}
inline void rotate(int x)
{
    int y=fa[x],w=son[y][1]==x;son[y][w]=son[x][w^1];
    if (son[x][w^1]) fa[son[x][w^1]]=y;
    if (fa[y]) 
        {
            int z=fa[y];
            if (son[z][0]==y) son[z][0]=x;
                else if (son[z][1]==y) son[z][1]=x;             
        }
    fa[x]=fa[y]; fa[y]=x; son[x][w^1]=y; update(y);
}
inline void splay(int x)
{
    int top=1,i=x,y; s[1]=i;
    while (!is_root(i)) s[++top]=i=fa[i];
    while (top) pb(s[top--]);
    while (!is_root(x))
        {
            y=fa[x];
            if (!is_root(y)) 
                if ((son[fa[y]][0]==y)^(son[y][0]==x)) rotate(x);else rotate(y);            
            rotate(x);
        }
    update(x);
}
inline void access(int x){for (int y=0; x; y=x,x=fa[x])splay(x),son[x][1]=y,update(x);}
inline void makeroot(int x){access(x),splay(x),rev1(x);}
inline void link(int x,int y){makeroot(x); fa[x]=y; access(x);}
inline void cutf(int x){access(x),splay(x);fa[son[x][0]]=0; son[x][0]=0; update(x);}
inline void cut(int x,int y){makeroot(x); cutf(y);}
inline void split(int x,int y){makeroot(x);access(y);splay(y);}
inline int find(int x){access(x);splay(x);while (son[x][0])x=son[x][0];return x;}
}col[110];
//Link Cut Tree
int main()
{
    n=read(),m=read(),c=read(),t=read();
    for (int u,v,w,i=1; i<=m; i++)
        {
            u=read(),v=read(),w=read(); if(u>v)swap(u,v);
            color[u][v]=w; colout[u][w]++; colout[v][w]++;
            col[w].link(u,v);
        }
    for (int x,y,z,i=1; i<=t; i++)
        {
            x=read(),y=read(),z=read(); if (x>y)swap(x,y);
            if (color[x][y]==z) {puts("Already owned.");continue;}
            if (!color[x][y]) {puts("No such cable.");continue;}
            if (colout[x][z]==2 || colout[y][z]==2) {puts("Forbidden: monopoly.");continue;}
            if (col[z].find(x)==col[z].find(y)) {puts("Forbidden: redundant.");continue;}
            puts("Sold."); col[color[x][y]].cut(x,y); col[z].link(x,y);
            colout[x][color[x][y]]--; colout[y][color[x][y]]--;
            colout[x][z]++;colout[y][z]++;color[x][y]=z;
        }
    return 0;
}

Creation August长者的模拟题...但是沙茶没调出来，大概是因为没有想到用map之类的去辅助处理，只想着一味的用LCT去解决全部问题...

还差的远呢！