NFLS-DAY 8

Posted on By 张, 高畅 NFLS-DAY 8无评论

T0

又到了亲爱的讲课时间了。
今天终于AK了练习题（泪目

T1

农夫约翰上个星期刚刚建好了他的新牛棚，他使用了最新的挤奶技术。不幸的是，由于工程问题，每个牛栏都不一样。第一个星期，农夫约翰随便地让奶牛们进入牛栏，但是问题很快地显露出来：每头奶牛都只愿意在她们喜欢的那些牛栏中产奶。上个星期，农夫约翰刚刚收集到了奶牛们的爱好的信息（每头奶牛喜欢在哪些牛栏产奶）。一个牛栏只能容纳一头奶牛，当然，一头奶牛只能在一个牛栏中产奶。
给出奶牛们的爱好的信息，计算最大分配方案。

模板，一个完美的匈牙利算法，就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=40005;
int n,m,match[N],st[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int find(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j]||find(match[j]))
            {
                match[j]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof h); 
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        int cnt;
        scanf("%d",&cnt);
        while(cnt--)
        {
            int x;
            scanf("%d",&x);
            add(i,x);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i))res++;
    }
    printf("%d",res);
    return 0;
}

T2

小 Q 是一个非常聪明的孩子，除了国际象棋，他还很喜欢玩一个电脑益智游戏――矩阵游戏。矩阵游戏在一个n×n的黑白方阵进行（如同国际象棋一般，只是颜色是随意的）。每次可以对该矩阵进行两种操作：
行交换操作：选择矩阵的任意两行，交换这两行（即交换对应格子的颜色）。
列交换操作：选择矩阵的任意两列，交换这两列（即交换对应格子的颜色）。
游戏的目标，即通过若干次操作，使得方阵的主对角线(左上角到右下角的连线)上的格子均为黑色。
对于某些关卡，小 Q 百思不得其解，以致他开始怀疑这些关卡是不是根本就是无解的！于是小 Q 决定写一个程序来判断这些关卡是否有解。

首先给出一个结论，实际上只要写行操作/列操作的任意一个就可以了。
如果行坐标无法完成，则列坐标其实也无法完成此操作。
于是，对于每一个黑格，连边连接行坐标与列坐标，剩下的套模板就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=40005;
int n,st[N],match[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int find(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j]||find(match[j]))
            {
                match[j]=u;
                return 1;
            }
        }
    }
    return 0;
}
void work()
{
    memset(match,0,sizeof match);
    memset(h,-1,sizeof h);
    idx=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            int x;
            scanf("%d",&x);
            if(x)add(i,j);
        }
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i))res++;
    }
    if(res==n)puts("Yes");
    else puts("No");
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

T3

有n*n的棋盘，上面有方格中有污点，一次可以把一行或者一列清洗干净，求最少的清洗次数。

求求了出题人下次出题的时候能不能按难度排序，一会儿简单一会难真的不好调还容易心态炸裂。
当然这题开始要掌握三个定理：

1.最大匹配数 = 最小点覆盖数（Konig定理）
2.最大独立数 = 最大匹配数
3.最小路径覆盖数 = 顶点数 – 最大匹配数

然后就没话说，连边直接连接行坐标与列坐标。

#include<bits/stdc++.h>
using namespace std;
const int N=505,M=250005;
int n,k,match[N],st[N];
int h[N],e[M],ne[M],idx;
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int find(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j]||find(match[j]))
            {
                match[j]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof h); 
    scanf("%d%d",&n,&k);
    while(k--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i))res++;
    }
    printf("%d",res);
    return 0;
}

T4

给定一个 01 矩阵，其中你可以在 0 的位置放置攻击装置。每一个攻击装置 (x,y) 都可以按照“日”字攻击其周围的 8 个位置 (x-1,y-2)，(x-2,y-1)，(x+1,y-2)，(x+2,y-1)，(x-1,y+2)，(x-2,y+1)，(x+1,y+2)，(x+2,y+1)。
求在装置互不攻击的情况下，最多可以放置多少个装置。

首先是这一题的一个小优化。
如果这样给图标号：
01010
10101
01010
10101
我们会发现，竟然标号为0的点总会攻击到标号为1的点，就可以只考虑0（或1）了，立省一半。
然后就是把二维的坐标hash一下变成一维，然后再去跑最大匹配。
最后跑的实际上是会有冲突的方案，最后再用总方案减去。

#include<bits/stdc++.h>
using namespace std;
const int N=205,M=80005,K=320005;
const int dx[8]={-1,-2,1,2,-1,-2,1,2};
const int dy[8]={-2,-1,-2,-1,2,1,2,1};
int n,res,st[M],p[M];
int h[M],e[K],ne[K],idx;
char s[N][N];
inline int get(int x,int y){return (x-1)*n+y;}
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!p[j]||dfs(p[j]))
            {
                p[j]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(s[i][j]=='0'&&(i+j)&1)
            {
                for(int k=0;k<8;k++)
                {
                    int nx=i+dx[k],ny=j+dy[k];
                    if(nx<1||ny<1||nx>n||ny>n||s[nx][ny]=='1')continue;
                    add(get(i,j),get(nx,ny));
                }
            }
            if(s[i][j]=='1')res++;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(s[i][j]=='0'&&(i+j)&1)
            {
                memset(st,0,sizeof st);
                if(dfs(get(i,j)))res++;
            }
        }
    }
    printf("%d",n*n-res);
    return 0;
}

T5

lanzerb 的部落在 A 国的上部，他们不满天寒地冻的环境，于是准备向A国的下部征战来获得更大的领土。
A 国是一个 M\times N 的矩阵，其中某些地方是城镇，某些地方是高山深涧无人居住。lanzerb 把自己的部落分成若干支军队，他们约定：
每支军队可以从任意一个城镇出发，并只能从上往向下征战，不能回头。途中只能经过城镇，不能经过高山深涧。
如果某个城镇被某支军队到过，则其他军队不能再去那个城镇了。
每支军队都可以在任意一个城镇停止征战。
所有军队都很奇怪，他们走的方法有点像国际象棋中的马。不过马每次只能走 1\times2 的路线，而他们只能走 R\times C 的路线。
lanzerb 的野心使得他的目标是统一全国，但是兵力的限制使得他们在配备人手时力不从心。假设他们每支军队都能顺利占领这支军队经过的所有城镇，请你帮 lanzerb 算算至少要多少支军队才能完成统一全国的大业。

与上一题类似，建图方式是类似的，可以参考上一题。

#include<bits/stdc++.h>
using namespace std;
const int N=55,M=100005,K=100005;
int dx[5],dy[5];
int n,m,r,c,sum,res,st[M],match[M];
int h[M],e[K],ne[K],idx;
char s[N][N];
inline int get(int x,int y){return (x-1)*m+y;}
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
int dfs(int u)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            st[j]=1;
            if(!match[j]||dfs(match[j]))
            {
                match[j]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d%d",&n,&m,&r,&c);
    dx[0]=r,dy[0]=c;
    dx[1]=r,dy[1]=-c;
    dx[2]=c,dy[2]=r;
    dx[3]=c,dy[3]=-r;
    for(int i=1;i<=n;i++)scanf("%s",s[i]+1);
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='.')
            {
                for(int k=0;k<4;k++)
                {
                    int nx=i+dx[k],ny=j+dy[k];
                    if(nx<1||ny<1||nx>n||ny>m||s[nx][ny]=='x')continue;
                    add(get(i,j),get(nx,ny));
                }
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            if(s[i][j]=='.')
            {
                memset(st,0,sizeof st);
                if(dfs(get(i,j)))res++;
                sum++;
            }
        }
    }
    printf("%d",sum-res);
    return 0;
}

T6

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。
一共两个子任务：
这张图是无向图。
这张图是有向图。

欧拉回路模板。

#include<bits/stdc++.h>
using namespace std;
const int N=100005,M=400005;
int type,n,m,h[N],e[M],ne[M],idx;
int used[M],res[M],cnt,din[N],dout[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void dfs(int u)
{
    for(int &i=h[u];~i;)
    {
        if(used[i])
        {
            i=ne[i];
            continue;
        }
        used[i]=1;
        if(type==1)used[i^1]=1;
        int u;
        if(type==1)
        {
            u=i/2+1;
            if(i&1)u=-u;
        }
        else u=i+1;
        int j=e[i];
        i=ne[i];
        dfs(j);
        res[++cnt]=u;
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d%d",&type,&n,&m);
    for(int i=0;i<m;i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        add(a,b);
        if(type==1)add(b,a);
        din[b]++;
        dout[a]++;
    }
    if(type==1)
    {
        for(int i=1;i<=n;i++)
        {
            if(din[i]+dout[i]&1)
            {
                puts("NO");
                return 0;
            }
        }
    }
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(din[i]!=dout[i])
            {
                puts("NO");
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(~h[i])
        {
            dfs(i);
            break;
        }
    }
    if(cnt<m)
    {
        puts("NO");
        return 0;
    }
    puts("YES");
    for(int i=cnt;i;i--)printf("%d ",res[i]);
    return 0;
}

T7

有N个盘子，每个盘子上写着一个仅由小写字母组成的英文单词。你需要给这些盘子安排一个合适的顺序，使得相邻两个盘子中，前一个盘子上单词的末字母等于后一个盘子上单词的首字母。请你编写一个程序，判断是否能达到这一要求。如果能，请给出一个合适的顺序。

这题建图方式是将每个单词看成一条边，首字母和为字母看成图中的顶点。
这样图是一个有向图，似乎又回到了上一题。

#include<bits/stdc++.h>
using namespace std;
const int N=35;
int n,m,din[N],dout[N],p[N],st[N];
int find(int x)
{
    if(p[x]==x)return x;
    else return p[x]=find(p[x]);
}
int main()
{
    char str[1005];
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        memset(din,0,sizeof din);
        memset(dout,0,sizeof dout);
        memset(st,0,sizeof st);
        for(int i=0;i<26;i++)p[i]=i;
        for(int i=0;i<n;i++)
        {
            scanf("%s",str);
            int len=strlen(str);
            int a=str[0]-'a',b=str[len-1]-'a';
            st[a]=st[b]=1;
            dout[a]++;
            din[b]++;
            p[find(a)]=find(b);
        }
        int bg=0,ed=0,flag=1;
        for(int i=0;i<26;i++)
        {
            if(din[i]!=dout[i])
            {
                if(din[i]==dout[i]+1)ed++;
                else if(din[i]+1==dout[i])bg++;
                else
                {
                    flag=0;
                    break;
                }
            }
        }
        if(flag&&!(!bg&&!ed||bg==1&&ed==1))flag=0;
        int r=-1;
        for(int i=0;i<26;i++)
        {
            if(st[i])
            {
                if(r==-1)r=find(i);
                else if(r!=find(i))
                {
                    flag=0;
                    break;
                }
            }
        }
        if(flag)puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
    return 0;
}

T8

给你无向图的N个点和M条边，保证这 条边都不同且不会存在同一点的自环边，现在问你至少要几笔才能所有边都画一遍。（一笔画的时候笔不离开纸）

没题出可以咬打火机，这题真的已经与模板关系不大，甚至代码都短的离谱。
并查集维护每一个联通块，记录内部的奇点数量（引出的边数是奇数）。
奇点数量<=2，用一笔就可以走完。
否则，要用(数量/2)笔才能走完。
累计就是答案。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,d[N],par[N],sum[N],ans[N];
int find(int x)
{
    if(par[x]==x)return x;
    else return par[x]=find(par[x]);
}
void work()
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
        d[i]=sum[i]=ans[i]=0;
    }
    while(m--)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        d[a]++;
        d[b]++;
        a=find(a),b=find(b);
        if(a==b)continue;
        par[a]=b;
    }
    for(int i=1;i<=n;i++)
    {
        int x=find(i);
        sum[x]++;
        if(d[i]%2)ans[x]++;
    }
    int res=0;
    for(int i=1;i<=n;i++)
    {
        if(sum[i]<=1)continue;
        if(ans[i]<=2)res++;
        else res+=ans[i]/2;
    }
    printf("%d\n",res);
}
int main()
{
    while(~scanf("%d%d",&n,&m))work();
    return 0;
}

T9

有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？

2-SAT模板稍微改一下。
设第i对夫妻，丈夫编号2i,妻子编号2i+1
然后没有矛盾的进行连边就可以了。

#include<bits/stdc++.h> 
using namespace std;
const int N=2e6+5;
int n,m;
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,Size[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    in_stk[u]=1;
    for(int i=h[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y=stk[top--];
            in_stk[y]=0;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }
        while(y!=u);
    }
}
int main()
{
    memset(h,-1,sizeof h);
    scanf("%d%d",&n,&m);
    while(m--)
    {
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        a=(a<<1)+c;
        b=(b<<1)+d;
        add(a,b^1);
        add(b,a^1);
        add(a^1,b^1);
    }
    for(int i=0;i<(n<<1);i++)
    {
        if(!dfn[i])tarjan(i);
    }
    for(int i=0;i<n;i++)
    {
        if(id[i*2]==id[i*2+1])
        {
            puts("NO");
            return 0;
        }
    }
    puts("YES");
    return 0;
}

T10

以下是一段代码
void go(int dep, int n, int m){
cout<<dep<<endl;
if (dep < m and x[a[dep]] + x[b[dep]] != c[dep])
go(dep + 1, n, m)
}
在这段代码中，n是一个整数，a、b、c和x都是四个整数数组。数组的索引始终从0开始。数组a和b由小于n的非负整数组成。数组x只包含0和1。数组c只包含0、1和2。数组a、b和c的长度为m，而数组x的长度为n。给定数组a、b和c的元素，当我们调用过程go(0, n, m)时，该过程可能输出的最大可能值是多少？

二分最多可以满足前几个询问。
然后做2-SAT。

#include<bits/stdc++.h> 
using namespace std;
const int N=40005;
int n;
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt;
int A[N],B[N],C[N];
void add(int a,int b){e[idx]=b,ne[idx]=h[a],h[a]=idx++;}
void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;
    in_stk[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j);
            low[u]=min(low[u],low[j]);
        }
        else if(in_stk[j])low[u]=min(low[u],dfn[j]);
    }
    if(dfn[u]==low[u])
    {
        ++scc_cnt;
        int y;
        do
        {
            y=stk[top--];
            in_stk[y]=0;
            id[y]=scc_cnt;
        }
        while(y!=u);
    }
}
int check(int m)
{
    memset(h,-1,sizeof h);
    memset(in_stk,0,sizeof in_stk);
    memset(dfn,0,sizeof dfn);
    memset(low,0,sizeof low);
    idx=timestamp=top=scc_cnt=0;
    for(int i=0;i<m;i++)
    {
        int a=A[i],b=B[i],c=C[i];
        if(!c)
        {
            add(a,b+n);
            add(b,a+n); 
        }
        else if(c==1)
        {
            add(a,b);
            add(b,a);
            add(a+n,b+n);
            add(b+n,a+n);
        }
        else
        {
            add(a+n,b);
            add(b+n,a);
        }
    }
    for(int i=0;i<2*n;i++)
    {
        if(!dfn[i])tarjan(i);
    }
    for(int i=0;i<n;i++)
    {
        if(id[i]==id[n+i])return 0;
    }
    return 1;
}
void work()
{
    int m;
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;i++)scanf("%d%d%d",&A[i],&B[i],&C[i]);
    int l=1,r=m;
    while(l<r)
    {
        int mid=l+r+1>>1;
        if(check(mid))l=mid;
        else r=mid-1;
    }
    printf("%d\n",l);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)work();
    return 0;
}

T11

大会的规则如下：每位参赛的选手可以得到N种材料，选手可以自由选择用满式或是汉式料理将材料当成菜肴。
大会的评审制度是：共有M位评审员分别把关。每一位评审员对于满汉全席有各自独特的见解，但基本见解是，要有两样菜色作为满汉全席的标志。如某评审认为，如果没有汉式东坡肉跟满式的涮羊肉锅，就不能算是满汉全席。但避免过于有主见的审核，大会规定一个评审员除非是在认为必备的两样菜色都没有做出来的状况下，才能淘汰一位选手，否则不能淘汰一位选手。
换句话说，只要参赛者能在这两种材料的做法中，其中一个符合评审的喜好即可通过该评审的审查。如材料有猪肉，羊肉和牛肉时，有四位评审员的喜好如下表：
评审一 评审二 评审三 评审四
满式牛肉 满式猪肉 汉式牛肉 汉式牛肉
汉式猪肉 满式羊肉 汉式猪肉 满式羊肉
如参赛者甲做出满式猪肉，满式羊肉和满式牛肉料理，他将无法满足评审三的要求，无法通过评审。而参赛者乙做出汉式猪肉，满式羊肉和满式牛肉料理，就可以满足所有评审的要求。
但大会后来发现，在这样的制度下如果材料选择跟派出的评审员没有特别安排好的话，所有的参赛者最多只能通过部分评审员的审查而不是全部，所以可能会发生没有人通过考核的情形。
如有四个评审员喜好如下表时，则不论参赛者采取什么样的做法，都不可能通过所有评审的考核：
评审一 评审二 评审三 评审四
满式羊肉 满式猪肉 汉式羊肉 汉式羊肉
汉式猪肉 满式羊肉 汉式猪肉 满式猪肉
所以大会希望有人能写一个程序来判断，所选出的N位评审，会不会发生没有人能通过考核的窘境，以便协会组织合适的评审团。

最后一题是最简单的。
就是2-SAT模板，处理一下读入就可以了。

#include <bits/stdc++.h>
using namespace std;
const int N = 40005;
int n;
int h[N], e[N], ne[N], idx;
int dfn[N], low[N], timestamp;
int stk[N], top, in_stk[N];
int id[N], scc_cnt;
void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; }
void tarjan(int u) {
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u;
    in_stk[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (!dfn[j]) {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        } else if (in_stk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u]) {
        ++scc_cnt;
        int y;
        do {
            y = stk[top--];
            in_stk[y] = 0;
            id[y] = scc_cnt;
        } while (y != u);
    }
}
void work() {
    memset(h, -1, sizeof h);
    memset(in_stk, 0, sizeof in_stk);
    memset(dfn, 0, sizeof dfn);
    memset(low, 0, sizeof low);
    idx = timestamp = top = scc_cnt = 0;
    int m;
    scanf("%d%d", &n, &m);
    while (m--) {
        int x, y;
        getchar();
        char ch1 = getchar();
        scanf("%d", &x);
        getchar();
        char ch2 = getchar();
        scanf("%d", &y);
        x--;
        y--;
        int a = (ch1 == 'h'), b = (ch2 == 'h');
        add(2 * x + !a, 2 * y + b);
        add(2 * y + !b, 2 * x + a);
    }
    for (int i = 0; i < 2 * n; i++) {
        if (!dfn[i])
            tarjan(i);
    }
    for (int i = 0; i < n; i++) {
        if (id[i * 2] == id[i * 2 + 1]) {
            puts("BAD");
            return;
        }
    }
    puts("GOOD");
}
int main() {
    int T;
    scanf("%d", &T);
    while (T--) work();
    return 0;
}

T∞

终于写完了，字数已经上1w了。
(话说我要是写作文写的有这么顺就好了)
毫无疑问，这一天的缓冲还是对我们有好处的。
至少我终于可以稍微补一下之前的题。

训练日志

发表回复