头像

bo-liever




离线:46分钟前


最近来访(47)
用户头像
哈夫曼的amazing
用户头像
BT7274
用户头像
灰之魔女伊蕾娜
用户头像
lofivo
用户头像
人间失格_1
用户头像
logs404
用户头像
PseudorandomGenerators
用户头像
金属
用户头像
StudyMachine
用户头像
yiwufeng
用户头像
Sorrymaker.
用户头像
qing123
用户头像
自律
用户头像
33号花卷
用户头像
edgdcgxgbx
用户头像
Rice_Porridge
用户头像
yhf
用户头像
handsomepyp
用户头像
Froggy
用户头像
灭却


bo-liever
46分钟前

(奇偶游戏)

#include<iostream>
#include<cstring>
#include<unordered_map>

using namespace std;

const int N=20010;

int n,m;
int p[N],d[N];
unordered_map<int,int> S;

int get(int x)
{
    if(S.count(x)==0) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if(p[x]!=x)
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}

int main()
{
    cin>>n>>m;
    n=0;

    for(int i=0;i<N;i++) p[i]=i;

    int res=m;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        string type;
        cin>>a>>b>>type;
        a=get(a-1),b=get(b);

        int t=0;
        if(type=="odd") t=1;

        int pa=find(a),pb=find(b);
        if(pa==pb)
        {
            if(((d[a]+d[b])%2+2)%2!=t)
            {
                res=i-1;
                break;
            }
        }
        else
        {
            p[pa]=pb;
            d[pa]=d[a]^d[b]^t;
        }
    }
    cout<<res<<endl;
    return 0;
}

(银河英雄传说)

#include<iostream>

using namespace std;

const int N=31010;

int m;
int p[N],SZ[N],d[N];

int find(int x)
{
    if(p[x]!=x)
    {
        int root=find(p[x]);
        d[x]+=d[p[x]];
        p[x]=root;
    }
    return p[x];
}

int main()
{
    cin>>m;

    for(int i=1;i<N;i++)
    {
        SZ[i]=1;
        p[i]=i;
    }
    while(m--)
    {
        char op[2];
        int a,b;
        cin>>op>>a>>b;

        if(op[0]=='M')
        {
            int pa=find(a),pb=find(b);
            d[pa]+=SZ[pb];
            SZ[pb]+=SZ[pa];
            p[pa]=pb;
        }
        else
        {
            int pa=find(a),pb=find(b);
            if(pa!=pb) puts("-1");
            else cout<<max(0,abs(d[a]-d[b])-1)<<endl;
        }
    }
    return 0;
}

(楼兰图腾)

#include<iostream>
#include<cstring>

using namespace std;

const int N=200010;

typedef long long LL;

int n;
int a[N];
int tr[N];
int Greater[N],Lower[N];

int lowbit(int x)
{
    return x&-x;
}

int add(int x,int c)
{
    for(int i=x;i<=n;i+=lowbit(i)) tr[i]+=c;
}

int sum(int x)
{
    int res=0;
    for(int i=x;i;i-=lowbit(i)) res+=tr[i];
    return res;
}

int main()
{
    cin>>n;

    for(int i=1;i<=n;i++) cin>>a[i];

    for(int i=1;i<=n;i++)
    {
        int y=a[i];
        Greater[i]=sum(n)-sum(y);
        Lower[i]=sum(y-1);
        add(y,1);
    }

    memset(tr,0,sizeof tr);
    LL res1=0,res2=0;
    for(int i=n;i;i--)
    {
        int y=a[i];
        res1+=Greater[i]*(LL)(sum(n)-sum(y));
        res2+=Lower[i]*(LL)(sum(y-1));
        add(y,1);
    }
    cout<<res1<<" "<<res2<<endl;
    return 0;
}



bo-liever
14小时前

(格子游戏)

#include<iostream>

using namespace std;

const int N=40010;

int n,m;
int p[N];

int get(int x,int y)
{
    return x*n+y;
}

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m;
    int x,y;
    int cnt=m;

    for(int i=0;i<n*n;i++) p[i]=i;
    int ans=0;
    while(m--)
    {
        int a,b;
        char D;
        cin>>x>>y>>D;
        x--,y--;
        a=get(x,y);
        if(D=='D')
            b=get(x+1,y);
        else
            b=get(x,y+1);

        int pa=find(a),pb=find(b);

        if(pa==pb)
        {
            ans=cnt-m;
            break;
        }
        else
            p[a]=p[b];
    }
    if(!ans) cout<<"draw"<<endl;
    else cout<<ans<<endl;

    return 0;
}

(搭配购买)

#include<iostream>
#include<cstring>

using namespace std;

const int N=10010;

int n,m,vol;
int p[N];
int w[N],v[N];
int f[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m>>vol;

    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=n;i++) cin>>v[i]>>w[i];

    while(m--)
    {
        int a,b;
        cin>>a>>b;
        int pa=find(a),pb=find(b);
        if(pa!=pb)
        {
            w[pb]+=w[pa];
            v[pb]+=v[pa];
            p[pa]=pb;
        }
    }

    for(int i=1;i<=n;i++)
        if(p[i]==i)
            for(int j=vol;j>=v[i];j--)
                f[j]=max(f[j],f[j-v[i]]+w[i]);

    cout<<f[vol]<<endl;
    return 0;
} 

(程序自动分析)

#include<iostream>
#include<unordered_map>

using namespace std;

const int N=2000010;

int n,m;
int p[N];
unordered_map<int,int> S;

struct Query
{
    int x,y,e;
}query[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int get(int x)
{
    if(S.count(x)==0) S[x]=++n;
    return S[x];
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        bool is_conflict=false;
        cin>>m;
        S.clear();
        n=0;

        for(int i=0;i<m;i++)
        {
            int x,y,e;
            cin>>x>>y>>e;
            query[i]={get(x),get(y),e};
        }

        for(int i=1;i<=n;i++) p[i]=i;

        for(int i=0;i<m;i++)
        {
            if(query[i].e==1)
            {
                int pa=find(query[i].x),pb=find(query[i].y);
                p[pa]=pb;
            }
        }

        for(int i=0;i<m;i++)
        {
            if(query[i].e==0)
            {
                int pa=find(query[i].x),pb=find(query[i].y);
                if(pa==pb)
                {
                    is_conflict=true;
                    break;
                }
            }
        }
        if(is_conflict) puts("NO");
        else puts("YES");
    }
    return 0;
}



bo-liever
16小时前

(奖金)

#include<iostream>
#include<cstring>

using namespace std;

const int N=10010,M=20010;

int n,m;
int h[N],e[M],ne[M],idx;
int dist[N];
int d[N];
int q[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

bool topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(!d[i])
            q[++tt]=i;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)
                q[++tt]=j;
        }
    }
    return tt==n-1;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(b,a);
        d[a]++;
    }

    if(!topsort()) puts("Poor Xed");
    else
    {
        for(int i=1;i<=n;i++) dist[i]=100;

        for(int i=0;i<n;i++)
        {
            int j=q[i];
            for(int k=h[j];~k;k=ne[k])
                dist[e[k]]=max(dist[e[k]],dist[j]+1);
        }

        int res=0;
        for(int i=1;i<=n;i++) res+=dist[i];
        cout<<res<<endl;
    }
    return 0;
}

(可达性统计)

#include<iostream>
#include<cstring>
#include<bitset>

using namespace std;

const int N=30010,M=30010;

int n,m;
int h[N],e[M],ne[M],idx;
int d[N];
int q[N];
bitset<N> f[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(!d[i])
            q[++tt]=i;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int j=h[t];~j;j=ne[j])
        {
            int k=e[j];
            if(--d[k]==0)
                q[++tt]=k;
        }
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        d[b]++;
    }

    topsort();

    for(int i=n-1;i>=0;i--)
    {
        int j=q[i];
        f[j][j]=1;
        for(int k=h[j];~k;k=ne[k])
        {
            f[j]|=f[e[k]];
        }
    }

    for(int i=1;i<=n;i++) cout<<f[i].count()<<endl;
    return 0;
}

(车站分级)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=2010,M=1000010;

int n,m;
int h[N],e[M],ne[M],w[M],idx;
int q[N],d[N];
int dist[N];
bool st[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
    d[b]++;
}

void topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=m+n;i++)
        if(!d[i])
            q[++tt]=i;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)
                q[++tt]=j;
        }
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(int i=1;i<=m;i++)
    {
        memset(st,0,sizeof st);
        int cnt;
        cin>>cnt;
        int start=n,end=1;
        while(cnt--)
        {
            int stop;
            cin>>stop;
            start=min(start,stop);
            end=max(end,stop);
            st[stop]=true;
        }

        int ver=n+i;
        for(int j=start;j<=end;j++)
            if(!st[j]) add(j,ver,0);
            else add(ver,j,1);
    }

    topsort();

    for(int i=1;i<=n;i++) dist[i]=1;
    for(int i=0;i<n+m;i++)
    {
        int j=q[i];
        for(int k=h[j];~k;k=ne[k])
            dist[e[k]]=max(dist[e[k]],dist[j]+w[k]);
    }

    int res=0;
    for(int i=1;i<=n;i++) res=max(res,dist[i]);

    cout<<res<<endl;
    return 0;
}



bo-liever
23小时前

(骑马修栅栏)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=510;

int n=500,m;
int g[N][N];
int ans[1100],cnt;
int d[N];

void dfs(int u)
{
    for(int i=1;i<=n;i++)
        if(g[u][i])
        {
            g[u][i]--,g[i][u]--;
            dfs(i);
        }
    ans[++cnt]=u;
}

int main()
{
    cin>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        g[a][b]++,g[b][a]++;
        d[a]++,d[b]++;
    }

    int start=1;
    while(!d[start]) start++;
    for(int i=1;i<=n;i++)
        if(d[i]%2)
        {
            start=i;
            break;
        }
    dfs(start);

    for(int i=cnt;i;i--) cout<<ans[i]<<endl;
    return 0;
}

(单词游戏)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=30;

int n;
int din[N],dout[N],p[N];
bool st[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    char str[1000];

    int T;
    cin>>T;
    while(T--)
    {
        cin>>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++)
        {
            cin>>str;
            int len=strlen(str);
            int a=str[0]-'a',b=str[len-1]-'a';
            st[a]=st[b]=true;
            dout[a]++,din[b]++;
            p[find(a)]=find(b);
        }

        int start=0,end=0;
        bool success=true;
        for(int i=0;i<26;i++)
            if(din[i]!=dout[i])
            {
                if(din[i]==dout[i]+1) end++;
                else if(din[i]+1==dout[i]) start++;
                else
                {
                    success=false;
                    break;
                }
            }

        if(success&&!(!start&&!end||start==1&&end==1)) success=false;

        int rep=-1;
        for(int i=0;i<26;i++)
            if(st[i])
            {
                if(rep==-1) rep=find(i);
                else if(rep!=find(i))
                {
                    success=false;
                    break;
                }
            }

        if(success) puts("Ordering is possible.");
        else puts("The door cannot be opened.");
    }
    return 0;
}

(家谱树)

#include<iostream>
#include<cstring>

using namespace std;

const int N=110,M=N*N;

int n;
int h[N],e[M],ne[M],idx;
int q[N];
int d[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void topsort()
{
    int hh=0,tt=-1;
    for(int i=1;i<=n;i++)
        if(!d[i])
            q[++tt]=i;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(--d[j]==0)
                q[++tt]=j;
        }
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);

    for(int i=1;i<=n;i++)
    {
        int son;
        while(cin>>son,son)
        {
            add(i,son);
            d[son]++;
        }
    }

    topsort();

    for(int i=0;i<n;i++) cout<<q[i]<<" ";
    cout<<endl;
    return 0;
}



(捉迷藏)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=210,M=30010;

int n,m;
bool d[N][N],st[N];
int match[N];

bool find(int x)
{
    for(int i=1;i<=n;i++)
        if(d[x][i]&&!st[i])
        {
            st[i]=true;
            int t=match[i];
            if(t==0||find(t))
            {
                match[i]=x;
                return true;
            }
        }
    return false;
}

int main()
{
    cin>>n>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        d[a][b]=true;
    }

    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                d[i][j]|=d[i][k]&d[k][j];

    int res=0;
    for(int i=1;i<=n;i++)
    {
        memset(st,0,sizeof st);
        if(find(i)) res++;
    }
    cout<<n-res<<endl;
    return 0;
}

(铲雪车)

#include<iostream>
#include<cmath>

using namespace std;

int main()
{
    double x1,y1,x2,y2;
    cin>>x1>>y1;

    double sum=0;
    while(cin>>x1>>y1>>x2>>y2)
    {
        double dx=x1-x2;
        double dy=y1-y2;
        sum+=sqrt(dx*dx+dy*dy)*2;
    }

    int minutes=round(sum/1000/20*60);
    int hours=minutes/60;
    minutes%=60;

    printf("%d:%02d\n",hours,minutes);
    return 0;
}

(欧拉回路)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010,M=400010;

int type;
int n,m;
int h[N],e[M],ne[M],idx;
bool used[M];
int ans[M],cnt;
int 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]=true;
        if(type==1) used[i^1]=true;

        int t;

        if(type==1)
        {
            t=i/2+1;
            if(i&1) t=-t;
        }
        else t=i+1;

        int j=e[i];
        i=ne[i];
        dfs(j);

        ans[++cnt]=t;
    }
}

int main()
{
    cin>>type;
    cin>>n>>m;
    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>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]!=-1)
        {
            dfs(i);
            break;
        }

    if(cnt<m)
    {
        puts("NO");
        return 0;
    }

    puts("YES");
    for(int i=cnt;i;i--) printf("%d ",ans[i]);
    puts("");

    return 0;
}




(棋盘覆盖)

#include<iostream>
#include<cstring>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=110;

int n,m;
PII match[N][N];
bool g[N][N],st[N][N];
int dx[4]={-1,0,1,0},dy[4]={0,1,0,-1};

bool find(int x,int y)
{
    for(int i=0;i<4;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a&&a<=n&&b&&b<=n&&!g[a][b]&&!st[a][b])
        {
            st[a][b]=true;
            PII t=match[a][b];
            if(t.x==-1||find(t.x,t.y))
            {
                match[a][b]={x,y};
                return true;
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;

    while(m--)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=true;
    }

    memset(match,-1,sizeof match);

    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if((i+j)%2&&!g[i][j])
            {
                memset(st,0,sizeof st);
                if(find(i,j)) res++;
            }
    cout<<res<<endl;
    return 0;
}

(机器任务)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=110;

int n,m,k;
int match[N];
bool g[N][N],st[N];

bool find(int x)
{
    for(int i=0;i<m;i++)
        if(!st[i]&&g[x][i])
        {
            st[i]=true;
            if(match[i]==-1||find(match[i]))
            {
                match[i]=x;
                return true;
            }
        }
    return false;
}

int main()
{
    while(cin>>n,n)
    {
        cin>>m>>k;
        memset(g,0,sizeof g);
        memset(match,-1,sizeof match);

        while(k--)
        {
            int t,a,b;
            cin>>t>>a>>b;
            if(!a||!b) continue;
            g[a][b]=true;
        }

        int res=0;
        for(int i=0;i<n;i++)
        {
            memset(st,0,sizeof st);
            if(find(i)) res++;
        }
        cout<<res<<endl;
    }
    return 0;
} 

(骑士放置)

#include<iostream>
#include<cstring>
#include<algorithm>

#define x first
#define y second

using namespace std;

typedef pair<int,int> PII;

const int N=110;

int n,m,k;
PII match[N][N];
bool g[N][N],st[N][N];

int dx[8]={-2,-1,1,2,2,1,-1,-2};
int dy[8]={1,2,2,1,-1,-2,-2,-1};

bool find(int x,int y)
{
    for(int i=0;i<8;i++)
    {
        int a=x+dx[i],b=y+dy[i];
        if(a<1||a>n||b<1||b>m) continue;
        if(g[a][b]) continue;
        if(st[a][b]) continue;

        st[a][b]=true;

        PII t=match[a][b];
        if(t.x==0||find(t.x,t.y))
        {
            match[a][b]={x,y};
            return true;
        }
    }
    return false;
}

int main()
{
    cin>>n>>m>>k;

    for(int i=0;i<k;i++)
    {
        int x,y;
        cin>>x>>y;
        g[x][y]=true;
    }

    int res=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            if(g[i][j]||(i+j)%2) continue;
            memset(st,0,sizeof st);
            if(find(i,j)) res++;
        }
    cout<<n*m-k-res<<endl;
    return 0;
}



(电力)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=10010,M=30010;

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int root,ans;

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;

    int cnt=0;
    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]);
            if(low[j]>=dfn[u]) cnt++;
        }
        else low[u]=min(low[u],dfn[j]);
    }
    if(u!=root) cnt++;
    ans=max(ans,cnt);
}

int main()
{
    while(cin>>n>>m,n||m)
    {
        memset(dfn,0,sizeof dfn);
        memset(h,-1,sizeof h);
        idx=timestamp=0;

        while(m--)
        {
            int a,b;
            cin>>a>>b;
            add(a,b),add(b,a);
        }

        ans=0;
        int cnt=0;
        for(root=0;root<n;root++)
            if(!dfn[root])
            {
                cnt++;
                tarjan(root);
            }
        cout<<ans+cnt-1<<endl;
    }
    return 0;
}

(矿场搭建)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef unsigned long long ULL;

const int N=1010,M=1010;

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int dcc_cnt;
vector<int> dcc[N];
bool cut[N];
int root;

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;

    if(u==root&&h[u]==-1)
    {
        dcc_cnt++;
        dcc[dcc_cnt].push_back(u);
        return;
    }

    int cnt=0;
    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]);
            if(dfn[u]<=low[j])
            {
                cnt++;
                if(u!=root||cnt>1) cut[u]=true;
                ++dcc_cnt;
                int y;
                do{
                    y=stk[top--];
                    dcc[dcc_cnt].push_back(y);
                }while(y!=j);
                dcc[dcc_cnt].push_back(u);
            }
        }
        else low[u]=min(low[u],dfn[j]);
    }
}

int main()
{
    int T=1;
    while(cin>>m,m)
    {
        for(int i=1;i<=dcc_cnt;i++) dcc[i].clear();
        idx=n=timestamp=top=dcc_cnt=0;
        memset(h,-1,sizeof h);
        memset(dfn,0,sizeof dfn);
        memset(cut,0,sizeof cut);

        while(m--)
        {
            int a,b;
            cin>>a>>b;
            n=max(n,a),n=max(n,b);
            add(a,b),add(b,a);
        }

        for(root=1;root<=n;root++)
            if(!dfn[root])
                tarjan(root);

        int res=0;
        ULL num=1;
        for(int i=1;i<=dcc_cnt;i++)
        {
            int cnt=0;
            for(int j=0;j<dcc[i].size();j++)
                if(cut[dcc[i][j]])
                    cnt++;

            if(cnt==0)
            {
                if(dcc[i].size()>1) res+=2,num*=dcc[i].size()*(dcc[i].size()-1)/2;
                else res++;
            }
            else if(cnt==1) res++,num*=dcc[i].size()-1;
        }
        printf("Case %d: %d %llu\n",T++,res,num);
    }
    return 0;
}

(关押罪犯)

#include<iostream>
#include<cstring>

using namespace std;

const int N=20010,M=200010;

int n,m;
int h[N],e[M],ne[M],w[M],idx;
int color[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

bool dfs(int u,int c,int mid)
{
    color[u]=c;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(w[i]<=mid) continue;
        if(color[j])
        {
            if(color[j]==c) return false;
        }
        else if(!dfs(j,3-c,mid)) return false;
    }
    return true;
}

bool check(int mid)
{
    memset(color,0,sizeof color);
    for(int i=1;i<=n;i++)
        if(!color[i])
            if(!dfs(i,1,mid)) return false;
    return true;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);

    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    int l=0,r=1e9;
    while(l<r)
    {
        int mid=l+r>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    cout<<r<<endl;
    return 0;
}



(最大半连通子图)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>

using namespace std;

typedef long long LL;

const int N=100010,M=2000010;

int n,m,mod;
int h[N],hs[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,scc_size[N];
int f[N],g[N];

void add(int h[],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]=true;

    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]=false;
            id[y]=scc_cnt;
            scc_size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);

    cin>>n>>m>>mod;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(h,a,b);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    unordered_set<LL> S;
    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            LL hash=a*1000000ll+b;
            if(a!=b&&!S.count(hash))
            {
                add(hs,a,b);
                S.insert(hash);
            }
        }

    for(int i=scc_cnt;i;i--)
    {
        if(!f[i])
        {
            f[i]=scc_size[i];
            g[i]=1;
        }

        for(int j=hs[i];~j;j=ne[j])
        {
            int k=e[j];
            if(f[k]<f[i]+scc_size[k])
            {
                f[k]=f[i]+scc_size[k];
                g[k]=g[i];
            }
            else if(f[k]==f[i]+scc_size[k])
                g[k]=(g[k]+g[i])%mod;
        }
    }

    int maxf=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
        if(f[i]>maxf)
        {
            maxf=f[i];
            sum=g[i];
        }
        else if(f[i]==maxf) sum=(sum+g[i])%mod;
    cout<<maxf<<endl;
    cout<<sum<<endl;
    return 0;
}

(银河)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<unordered_set>

using namespace std;

typedef long long LL;

const int N=100010,M=600010;

int n,m;
int h[N],hs[N],e[M],ne[M],w[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt,sz[N];
int dist[N];

void add(int h[],int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u,in_stk[u]=true;

    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]=false;
            id[y]=scc_cnt;
            sz[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(hs,-1,sizeof hs);

    for(int i=1;i<=n;i++) add(h,0,i,1);

    while(m--)
    {
        int t,a,b;
        cin>>t>>a>>b;
        if(t==1) add(h,b,a,0),add(h,a,b,0);
        else if(t==2) add(h,a,b,1);
        else if(t==3) add(h,b,a,0);
        else if(t==4) add(h,b,a,1);
        else add(h,a,b,0);
    }

    tarjan(0);

    bool success=true;
    for(int i=0;i<=n;i++)
    {
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a==b)
            {
                if(w[j]>0)
                {
                    success=false;
                    break;
                }
            }
            else add(hs,a,b,w[j]);
        }
        if(!success) break;
    }

    if(!success) puts("-1");
    else
    {
        for(int i=scc_cnt;i;i--)
        {
            for(int j=hs[i];~j;j=ne[j])
            {
                int k=e[j];
                dist[k]=max(dist[k],dist[i]+w[j]);
            }
        }

        LL res=0;

        for(int i=1;i<=scc_cnt;i++) res+=(LL) dist[i]*sz[i];

        cout<<res<<endl;
    }
    return 0;
}

(冗余路径)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=5010,M=20010;

int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
int is_bridge[M];
int d[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void tarjan(int u,int from)
{
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;

    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!dfn[j])
        {
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(dfn[u]<low[j])
                is_bridge[i]=is_bridge[i^1]=true;
        }
        else if(i!=(from^1))
            low[u]=min(low[u],dfn[j]);
    }

    if(dfn[u]==low[u])
    {
        ++dcc_cnt;
        int y;
        do{
            y=stk[top--];
            id[y]=dcc_cnt;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }

    tarjan(1,-1);

    for(int i=0;i<idx;i++)
        if(is_bridge[i])
            d[id[e[i]]]++;

    int cnt=0;
    for(int i=1;i<=dcc_cnt;i++)
        if(d[i]==1)
            cnt++;

    cout<<(cnt+1)/2<<endl;
    return 0;
}



(闇の連鎖)

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010,M=N*2;

int n,m;
int h[N],e[M],ne[M],idx;
int depth[N],fa[N][17];
int d[N];
int q[N];
int ans;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    int hh=0,tt=0;
    q[0]=1;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[++tt]=j;
                fa[j][0]=t;
                for(int k=1;k<=16;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=16;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}

int dfs(int u,int father)
{
    int res=d[u];
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j!=father)
        {
            int s=dfs(j,u);
            if(s==0) ans+=m;
            else if(s==1) ans++;
            res+=s;
        }
    }
    return res;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b;
        cin>>a>>b;
        add(a,b),add(b,a);
    }

    bfs();

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        int p=lca(a,b);
        d[a]++,d[b]++,d[p]-=2;
    }
    dfs(1,-1);
    cout<<ans<<endl;
    return 0;
}

(受欢迎的牛)

#include<iostream>
#include<cstring>

using namespace std;

const int N=10010,M=5*N;

int n,m;
int h[N],e[M],ne[M],idx;
bool in_stk[N];
int stk[N],top;
int dfn[N],low[N],timestamp;
int id[N],Size[N],scc_cnt;
int dout[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]=true;
    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]=false;
            id[y]=scc_cnt;
            Size[scc_cnt]++;
        }while(y!=u);
    }
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b) dout[a]++;
        }

    int zeros=0,sum=0;
    for(int i=1;i<=scc_cnt;i++)
        if(!dout[i])
        {
            zeros++;
            sum+=Size[i];
            if(zeros>1)
            {
                sum=0;
                break;
            }
        }
    cout<<sum<<endl;
    return 0;
}

(学校网络)

#include<iostream>
#include<cstring>

using namespace std;

const int N=110,M=10010;

int n;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
bool in_stk[N];
int id[N],scc_cnt;
int din[N],dout[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]=true;

    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]=false;
            id[y]=scc_cnt;
        }while(y!=u);
    }
}

int main()
{
    cin>>n;
    memset(h,-1,sizeof h);
    for(int i=1;i<=n;i++)
    {
        int t;
        while(cin>>t,t) add(i,t);
    }

    for(int i=1;i<=n;i++)
        if(!dfn[i])
            tarjan(i);

    for(int i=1;i<=n;i++)
        for(int j=h[i];~j;j=ne[j])
        {
            int k=e[j];
            int a=id[i],b=id[k];
            if(a!=b)
            {
                dout[a]++;
                din[b]++;
            }
        }

    int a=0,b=0;
    for(int i=1;i<=scc_cnt;i++)
    {
        if(!din[i]) a++;
        if(!dout[i]) b++;
    }

    cout<<a<<endl;
    if(scc_cnt==1) puts("0");
    else printf("%d\n",max(a,b));
    return 0;
}



(祖孙询问)

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=40010,M=2*N;

int n,m;
int q[N];
int h[N],e[M],ne[M],idx;
int fa[N][16],depth[N];

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

void bfs(int root)
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[root]=1;
    int hh=0,tt=0;
    q[0]=root;

    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[++tt]=j;
                fa[j][0]=t;
                for(int k=1;k<=15;k++)
                    fa[j][k]=fa[fa[j][k-1]][k-1];
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=15;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
            a=fa[a][k];
    if(a==b) return a;
    for(int k=15;k>=0;k--)
        if(fa[a][k]!=fa[b][k])
        {
            a=fa[a][k];
            b=fa[b][k];
        }
    return fa[a][0];
}

int main()
{
    cin>>n;
    int root=0;
    memset(h,-1,sizeof h);

    for(int i=0;i<n;i++)
    {
        int a,b;
        cin>>a>>b;
        if(b==-1) root=a;
        else add(a,b),add(b,a);
    }

    bfs(root);

    cin>>m;
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        int p=lca(a,b);
        if(p==a) puts("1");
        else if(p==b) puts("2");
        else puts("0");
    }
    return 0;
}

(距离)

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

typedef pair<int,int> PII;

const int N=10010,M=2*N;

int n,m;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
int p[N];
int res[M];
int st[N];
vector<PII> query[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

void dfs(int u,int fa)
{
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(j==fa) continue;
        dist[j]=dist[u]+w[i];
        dfs(j,u);
    }
}


int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void tarjan(int u)
{
    st[u]=1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        if(!st[j])
        {
            tarjan(j);
            p[j]=u;
        }
    }

    for(auto item:query[u])
    {
        int y=item.first,id=item.second;
        if(st[y]==2)
        {
            int anc=find(y);
            res[id]=dist[u]+dist[y]-dist[anc]*2;
        }
    }
    st[u]=2;
}

int main()
{
    cin>>n>>m;
    memset(h,-1,sizeof h);
    for(int i=0;i<n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c),add(b,a,c);
    }

    for(int i=0;i<m;i++)
    {
        int a,b;
        cin>>a>>b;
        if(a!=b)
        {
            query[a].push_back({b,i});
            query[b].push_back({a,i});
        }
    }

    for(int i=1;i<=n;i++) p[i]=i;

    dfs(1,-1);
    tarjan(1);

    for(int i=0;i<m;i++) cout<<res[i]<<endl;
    return 0;
}

(次小生成树)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

typedef long long LL;

const int N=100010,M=300010,INF=0x3f3f3f3f;

int n,m;
struct Edge
{
    int a,b,w;
    bool used;
    bool operator<(const Edge &t)const
    {
        return w<t.w;
    }
}edge[M];
int p[N];
int h[N],e[M],ne[M],w[M],idx;
int depth[N],fa[N][17],d1[N][17],d2[N][17];
int q[N];

void add(int a,int b,int c)
{
    e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

LL kruskal()
{
    for(int i=1;i<=n;i++) p[i]=i;
    sort(edge,edge+m);
    LL res=0;
    for(int i=0;i<m;i++)
    {
        int a=find(edge[i].a),b=find(edge[i].b),w=edge[i].w;
        if(a!=b)
        {
            p[a]=b;
            res+=w;
            edge[i].used=true;
        }
    }
    return res;
}

void build()
{
    memset(h,-1,sizeof h);
    for(int i=0;i<m;i++)
        if(edge[i].used)
        {
            int a=edge[i].a,b=edge[i].b,w=edge[i].w;
            add(a,b,w),add(b,a,w);
        }
}

void bfs()
{
    memset(depth,0x3f,sizeof depth);
    depth[0]=0,depth[1]=1;
    q[0]=1;
    int hh=0,tt=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];~i;i=ne[i])
        {
            int j=e[i];
            if(depth[j]>depth[t]+1)
            {
                depth[j]=depth[t]+1;
                q[++tt]=j;
                fa[j][0]=t;
                d1[j][0]=w[i],d2[j][0]=-INF;
                for(int k=1;k<=16;k++)
                {
                    int anc=fa[j][k-1];
                    fa[j][k]=fa[anc][k-1];
                    int distance[4]={d1[j][k-1],d2[j][k-1],d1[anc][k-1],d2[anc][k-1]};
                    d1[j][k]=d2[j][k]=-INF;
                    for(int u=0;u<4;u++)
                    {
                        int d=distance[u];
                        if(d>d1[j][k]) d2[j][k]=d1[j][k],d1[j][k]=d;
                        else if(d!=d1[j][k]&&d>d2[j][k]) d2[j][k]=d;
                    }
                }
            }
        }
    }
}

int lca(int a,int b,int w)
{
    static int distance[N*2];
    int cnt=0;
    if(depth[a]<depth[b]) swap(a,b);
    for(int k=16;k>=0;k--)
        if(depth[fa[a][k]]>=depth[b])
        {
            distance[cnt++] =d1[a][k];
            distance[cnt++]=d2[a][k];
            a=fa[a][k];
        }
    if(a!=b)
    {
        for(int k=16;k>=0;k--)
            if(fa[a][k]!=fa[b][k])
            {
                distance[cnt++]=d1[a][k];
                distance[cnt++]=d2[a][k];
                distance[cnt++]=d1[b][k];
                distance[cnt++]=d2[b][k];
                a=fa[a][k],b=fa[b][k];
            }
        distance[cnt++]=d1[a][0];
        distance[cnt++]=d1[b][0];
    }

    int dist1=-INF,dist2=-INF;
    for(int i=0;i<cnt;i++)
    {
        int d=distance[i];
        if(d>dist1) dist2=dist1,dist1=d;
        else if(d!=dist1&&d>dist2) dist2=d;
    }

    if(w>dist1) return w-dist1;
    if(w>dist2) return w-dist2;
    return INF;
}

int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }

    LL sum=kruskal();
    build();
    bfs();

    LL res=1e18;
    for(int i=0;i<m;i++)
        if(!edge[i].used)
        {
            int a=edge[i].a,b=edge[i].b,w=edge[i].w;
            res=min(res,sum+lca(a,b,w));
        }
    printf("%lld\n",res);
    return 0;
}