贝壳找房魔法师顾问 2018 计蒜之道 复赛

https://nanti.jisuanke.com/t/A1725

 

V&V

无向图

强连通图

每个子图，n个点，选择n-1条，使互相连接

因为目标点x->点y，可以改为点y->点x

 

V&C

弱连通图(将有向图的所有的有向边替换为无向边，所得到的图称为原图的基图。如果一个有向图的基图是连通图，则有向图是弱连通图。)

1.一个弱连通子图，它里面的点与该弱连通子图外的点与没有关系，可以单独处理

2.弱连通子图里，一个点，必有另外点与之相邻，包括入和出

3.若弱连通子图里有环，则无论怎么修改，避免不了最后的图，有环的情况(因为需求无法改变，x指向y，则从x出发，必有路径到y)，

对于环外剩下的点，也必至少有一条边，总边数大于等于点数

4.对于弱连通子图的点，可以构造一个环，使它们相互可以到达，需要的边的数量为点数

5.所以对于有环的弱连通子图，选择4的方案，构造环

6.对于没有环的弱连通子图，求拓扑排序，从小到大赋予编号，

按照编号，点1连接，点2连接点3，...，点p-1连接点p，满足条件。

对于边，必定是编号小的点连接编号大的点，所以没有产生遗漏。

需要的边的数量为点数-1

 

如

6
Constant 1 2 3 1 2 3
Variable 4 4 4 5 5 5

 

 计蒜客好像不能开以下优化，差评：

    ios_base::sync_with_stdio(0);
    cin.tie(0);

 

///所以参加比赛时，先测试一下这些能不能用

 

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
#define ll long long
#include <map>

const double eps=1e-8;
const ll inf=1e9;
const ll mod=1e9+7;
const int maxn=1e5+10;

struct node
{
    int d;
    node *to;
}*e[maxn],*b[maxn];

string c[2];
int s[2][maxn],tot[maxn],q[maxn];
bool vis[maxn];

map<pair<int,int>,int> ma;

int main()
{
//    ios_base::sync_with_stdio(0);
//    cin.tie(0);

    node *p;
    int n,i,j,k,x,y,cnt=0;
    int head,tail,d,temp;
    scanf("%d",&n);
    k=0;
    for (j=0;j<2;j++)
    {
        cin>>c[j];
        if (j==0 && c[0][0]=='C')
            k=1;

        for (i=1;i<=n;i++)
            cin>>s[j^k][i];
    }
    if (k==1)
        swap(c[0],c[1]);

    if (c[0][0]=='C' && c[1][0]=='C')
    {
        for (i=1;i<=n;i++)
            if (s[0][i]!=s[1][i])
                break;
        if (i==n+1)
            cout<<0;
        else
            cout<<-1;
    }
    else if (c[1][0]=='C')
    {
        for (i=1;i<=n;i++)
        {
            x=s[0][i];
            y=s[1][i];
            if (x==y || ma.find({x,y})!=ma.end())
                continue;
            ma[{x,y}]=1;
            p=new node();
            p->d=y;
            p->to=e[x];
            e[x]=p;

            p=new node();
            p->d=x;
            p->to=e[y];
            e[y]=p;
            tot[y]++;

            p=new node();
            p->d=y;
            p->to=b[x];
            b[x]=p;

        }

        for (i=1;i<=1e5;i++)
            if (!vis[i] && e[i])
            {
                q[1]=i;
                vis[i]=1;
                head=0,tail=1;
                while (head<tail)
                {
                    d=q[++head];
                    p=e[d];
                    while (p)
                    {
                        if (!vis[p->d])
                        {
                            vis[p->d]=1;
                            q[++tail]=p->d;
                        }
                        p=p->to;
                    }
                }

                temp=tail;
                head=0,tail=0;
                for (j=1;j<=temp;j++)
                    if (!tot[q[j]])
                        q[++tail]=q[j];

                ///if no loop, traversal tail points
                while (head<tail)
                {
                    head++;
                    d=q[head];
                    p=b[d];///
                    while (p)
                    {
                        tot[p->d]--;
                        if (!tot[p->d])
                            q[++tail]=p->d;
                        p=p->to;
                    }
                }
                cnt+=temp-(tail==temp);
            }
        cout<<cnt;
    }
    else
    {
        for (i=1;i<=n;i++)
        {
            x=s[0][i];
            y=s[1][i];
            if (x==y)
                continue;
            p=new node();
            p->d=y;
            p->to=e[x];
            e[x]=p;

            p=new node();
            p->d=x;
            p->to=e[y];
            e[y]=p;
        }

        for (i=1;i<=1e5;i++)
            if (!vis[i] && e[i])
            {
                q[1]=i;
                vis[i]=1;
                head=0,tail=1;
                while (head<tail)
                {
                    d=q[++head];
                    p=e[d];
                    while (p)
                    {
                        if (!vis[p->d])
                        {
                            vis[p->d]=1;
                            q[++tail]=p->d;
                        }
                        p=p->to;
                    }
                }
                cnt+=tail-1;
            }
        cout<<cnt;
    }
    return 0;
}
/*
2
Constant 111 222
Constant 111 223

2
Constant 111 222
Constant 111 222

5
Variable 111 222 333 444 555
Variable 222 333 111 444 666

5
Constant 111 222 333 444 333
Variable 222 111 444 555 666

5
Variable 222 111 444 555 666
Constant 111 222 333 444 333

7
Variable 222 111 444 555 666 444 444
Constant 111 222 333 444 333 666 555

3
Variable 111 111 111
Variable 222 222 222

4
Constant 333 111 111 111
Variable 333 222 222 222

6
Constant 1 2 3 1 2 3
Variable 4 4 4 5 5 5

6
Variable 1 2 3 1 2 3
Variable 4 4 4 5 5 5

3
Variable 1 2 3
Variable 4 5 6

3
Constant 1 2 3
Variable 4 5 6
*/