头像

xty




离线:10小时前


最近来访(136)
用户头像
拼凑未来
用户头像
fighting_20484
用户头像
顽童
用户头像
SL_hjp
用户头像
1033200128
用户头像
LNN
用户头像
RA
用户头像
renaissance.
用户头像
小镇做题家qwq
用户头像
抒怀
用户头像
zz哲
用户头像
tommy_
用户头像
一期一会
用户头像
no_one
用户头像
nya
用户头像
橙子霖
用户头像
一笙_
用户头像
老当益壮
用户头像
Ariesfun
用户头像
不给大雪菜main子

活动打卡代码 AcWing 257. 关押罪犯

xty
8天前
#include <bits/stdc++.h>
using namespace std;

const int N = 20010,M = 200010;
int h[N],e[M],ne[M],w[M],idx;
int color[N];
int n,m;

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 != -1;i = ne[i])
    {
        int j = e[i];

        if(w[i] <= mid)
            continue;

        if(!color[j])
        {
            if(!dfs(j,3 - c,mid))
                return false;
        }
        else if(c == color[j])
            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()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h, -1, sizeof h);

    cin >> n >> m;

    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;

    return 0;
}


活动打卡代码 AcWing 396. 矿场搭建

xty
8天前
#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;

const int N = 1010;
int h[N],e[N],ne[N],idx;
int dfn[N],low[N],dcc_cnt,timecamp;
bool st[N];
vector<int> g[N];
stack<int> s;
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] = ++ timecamp;
    s.push(u);

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

    int cnt = 0;

    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]);
            if(dfn[u] <= low[j])
            {
                cnt ++;
                if(u != root || cnt > 1)
                    st[u] = true;

                int y;
                dcc_cnt ++;
                do
                {
                    y = s.top();
                    s.pop();
                    g[dcc_cnt].push_back(y);
                }while(y != j);
                g[dcc_cnt].push_back(u);
            }
        }
        else
            low[u] = min(low[u],dfn[j]);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    int n,m,t = 1;
    while(cin >> m,m)
    {

        memset(h,-1,sizeof h);
        memset(st,false,sizeof st);
        memset(dfn,0,sizeof dfn);
        while(!s.empty()) s.pop();
        for(int i = 1;i <= dcc_cnt;i++)
            g[i].clear();
        idx = dcc_cnt = timecamp = n = 0;

        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 res2 = 1;

        for(int i = 1;i <= dcc_cnt;i++)
        {
            int cnt = 0;

            for(int j = 0;j < g[i].size();j++)
            {
                if(st[g[i][j]])
                    cnt ++;
            }

            if(cnt == 0)
                if(g[i].size() > 1)
                    res += 2,res2 *= g[i].size() * (g[i].size() - 1) / 2;
                else
                    res ++;
            else if(cnt == 1)
                res ++,res2 *= g[i].size() - 1;
        }

        cout << "Case " << t ++ << ": " << res << " " << res2 << endl;
    }

    return 0;
}


活动打卡代码 AcWing 1183. 电力

xty
8天前
#include <bits/stdc++.h>
using namespace std;

const int N = 10010,M = 30010;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timecamp;
int ans,root;
stack<int> s;

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

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timecamp;
    s.push(u);

    int cnt = 0;

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

    if(u != root)
        cnt ++;

    ans = max(ans,cnt);
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

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

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

            add(a,b),add(b,a);
        }

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

        cout << ans + cnt - 1 << endl;
    }

    return 0;
}


活动打卡代码 AcWing 395. 冗余路径

xty
8天前
#include <bits/stdc++.h>
using namespace std;

const int N = 5010,M = 20010;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],id[N],d[N],dcc_cnt,timecamp;
bool st[N];
stack<int> s;

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] = ++ timecamp;
    s.push(u);

    for(int i = h[u];i != -1;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])
                st[i] = st[i ^ 1] = true;
        }
        else if(i != (from ^ 1))
            low[u] = min(low[u],dfn[j]);
    }

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

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h, -1, sizeof h);

    int n,m;
    cin >> n >> m;

    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(st[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;

    return 0;
}


活动打卡代码 AcWing 368. 银河

xty
13天前
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e5 + 5,M = 6e5 + 5;
int h[N],h2[N],e[M],ne[M],w[M],idx;
int dfn[N],low[N],id[N],Size[N],d[N],scc_cnt,timecamp;
bool st[N];
stack<int> s;

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] = ++ timecamp;
    s.push(u);
    st[u] = true;

    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(st[j])
            low[u] = min(low[u],dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        int y;
        scc_cnt ++;

        do
        {
            y = s.top();
            s.pop();
            st[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        }while(y != u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h,-1,sizeof h);
    memset(h2,-1,sizeof h2);

    int n,m;
    cin >> n >> m;

    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,a,b,0),add(h,b,a,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++)
    {
        if(!success)
            break;

        for(int j = h[i];j != -1;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(h2,a,b,w[j]);
        }
    }

    if(!success)
        cout << -1;
    else
    {
        for(int i = scc_cnt;i;i--)
        {
            for(int j = h2[i];j != -1;j = ne[j])
            {
                int k = e[j];

                d[k] = max(d[k],d[i] + w[j]);
            }
        }

        LL res = 0;
        for(int i = 1;i <= scc_cnt;i++)
            res += (LL)d[i] * Size[i];

        cout << res;
    }

    return 0;
}



xty
13天前
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 1e5 + 5,M = 2e6 + 5;
int h[N],h2[N],e[M],ne[M],idx;
int dfn[N],low[N],Size[N],id[N],scc_cnt,timecamp;
int f[N],g[N];
bool st[N];
stack<int> s;
unordered_set<LL> mp;


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] = ++ timecamp;
    s.push(u);
    st[u] = true;

    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(st[j])
            low[u] = min(low[u],dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        scc_cnt ++;
        int y;
        do
        {
            y = s.top();
            s.pop();
            st[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        }while(y != u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h,-1,sizeof h);
    memset(h2,-1,sizeof h2);

    int n,m,mod;
    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);

    for(int i = 1;i <= n;i++)
    {
        for(int j = h[i];j != -1;j = ne[j])
        {
            int k = e[j];

            int a = id[i],b = id[k];

            LL hash = (LL)a * 1e6 + b;
            if(a != b && !mp.count(hash))
            {
                add(h2,a,b);
                mp.insert(hash);
            }
        }
    }

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

        for(int j = h2[i];j != -1;j = ne[j])
        {
            int k = e[j];

            if(f[k] < f[i] + Size[k])
            {
                f[k] = f[i] + Size[k];
                g[k] = g[i];
            }
            else if(f[k] == f[i] + Size[k])
                g[k] = (g[k] + g[i]) % mod;
        }
    }

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

    cout << maxk << endl << sum;

    return 0;
}


活动打卡代码 AcWing 367. 学校网络

xty
13天前
#include <bits/stdc++.h>
using namespace std;

const int N = 110,M = 1010;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],din[N],dout[N],id[N],scc_cnt,timecmap;
bool st[N];
stack<int> s;

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

void tarjan(int u,int pre)
{
    dfn[u] = low[u] = ++ timecmap;
    s.push(u);
    st[u] = true;

    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];

        if(j == u)
            continue;

        if(!dfn[j])
        {
            tarjan(j,u);
            low[u] = min(low[u],low[j]);
        }
        else if(st[j])
            low[u] = min(low[u],dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        scc_cnt ++;
        int y;
        do
        {
            y = s.top();
            s.pop();
            st[y] = false;
            id[y] = scc_cnt;
        }while(y != u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h,-1,sizeof h);

    int n;
    cin >> n;

    for(int i = 1;i <= n;i++)
    {
        int a;
        while(cin >> a,a)
            add(i,a);
    }

    int res1 = 0,res2 = 0;

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

    for(int i = 1;i <= n;i++)
    {
        for(int j = h[i];j != -1;j = ne[j])
        {
            int k = e[j];

            int a = id[i],b = id[k];

            if(a != b)
                dout[a] ++,din[b] ++;
        }
    }

    for(int i = 1;i <= scc_cnt;i++)
        if(!din[i])
            res1 ++;

    if(scc_cnt > 1)
    {
        for(int i = 1;i <= scc_cnt;i++)
            if(!dout[i])
                res2 ++;
        res2 = max(res2,res1);
    }

    cout << res1 << endl << res2;

    return 0;
}


活动打卡代码 AcWing 367. 学校网络

xty
13天前
#include <bits/stdc++.h>
using namespace std;

const int N = 110,M = 1010;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],din[N],dout[N],id[N],scc_cnt,timecmap;
bool st[N];
stack<int> s;

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

void tarjan(int u,int pre)
{
    dfn[u] = low[u] = ++ timecmap;
    s.push(u);
    st[u] = true;

    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];

        if(j == u)
            continue;

        if(!dfn[j])
        {
            tarjan(j,u);
            low[u] = min(low[u],low[j]);
        }
        else if(st[j])
            low[u] = min(low[u],dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        scc_cnt ++;
        int y;
        do
        {
            y = s.top();
            s.pop();
            st[y] = false;
            id[y] = scc_cnt;
        }while(y != u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h,-1,sizeof h);

    int n;
    cin >> n;

    for(int i = 1;i <= n;i++)
    {
        int a;
        while(cin >> a,a)
            add(i,a);
    }

    int res1 = 0,res2 = 0;

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

    for(int i = 1;i <= n;i++)
    {
        for(int j = h[i];j != -1;j = ne[j])
        {
            int k = e[j];

            int a = id[i],b = id[k];

            if(a != b)
                dout[a] ++,din[b] ++;
        }
    }

    for(int i = 1;i <= scc_cnt;i++)
        if(!din[i])
            res1 ++;

    if(scc_cnt > 1)
    {
        for(int i = 1;i <= scc_cnt;i++)
            if(!dout[i])
                res2 ++;
        res2 = max(res2,res1);
    }

    cout << res1 << endl << res2;

    return 0;
}


活动打卡代码 AcWing 1174. 受欢迎的牛

xty
13天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e4 + 5,M = 5e4 + 5;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],id[N],Size[N],dout[N],scc_cnt,timestamp;
stack<int> s;
bool st[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;
    s.push(u);
    st[u] = true;

    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(st[j])
            low[u] = min(low[u],dfn[j]);
    }

    if(dfn[u] == low[u])
    {
        scc_cnt ++;
        int y;        
        do
        {
            y = s.top();
            s.pop();
            st[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        }while(y != u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    memset(h,-1,sizeof h);

    int n,m;
    cin >> n >> m;

    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 != -1;j = ne[j])
        {
            int k = e[j];
            int a = id[i],b = id[k];

            if(a != b)
                dout[a] ++;
        }
    }

    int sum = 0,cnt = 0;
    for(int i = 1;i <= scc_cnt;i++)
        if(!dout[i])
        {
            cnt ++;
            sum += Size[i];

            if(cnt > 1)
            {
                sum = 0;
                break;
            }
        }

    cout << sum;

    return 0;
}


活动打卡代码 AcWing 352. 闇の連鎖

xty
15天前
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5,M = 2e5 + 5;
int h[N],e[M],ne[M],idx;
int d[N],depth[N],f[N][17];
int n,m,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;

    queue<int> q;
    q.push(1);

    while(q.size())
    {
        int t = q.front();
        q.pop();

        for(int i = h[t];i != -1;i = ne[i])
        {
            int j = e[i];

            if(depth[j] > depth[t] + 1)
            {
                depth[j] = depth[t] + 1;
                f[j][0] = t;
                q.push(j);

                for(int k = 1;k <= 16;k++)
                    f[j][k] = f[f[j][k - 1]][k - 1];
            }
        }
    }
}

int lca(int a,int b)
{
    if(depth[a] < depth[b])
        swap(a,b);

    for(int i = 16;i >= 0;i--)
    {
        if(depth[f[a][i]] >= depth[b])
            a = f[a][i];
    }

    if(a == b)
        return a;

    for(int i = 16;i >= 0;i--)
    {
        if(f[a][i] != f[b][i])
        {
            a = f[a][i];
            b = f[b][i];
        }
    }

    return f[a][0];
}

int dfs(int u,int fa)
{
    int res = d[u];

    for(int i = h[u];i != -1;i = ne[i])
    {
        int j = e[i];

        if(j == fa)
            continue;

        int s = dfs(j,u);
        if(s == 0)
            ans += m;
        else if(s == 1)
            ans ++;

        res += s;
    }

    return res;
}

int main()
{
    std::ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);

    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;

    return 0;
}