头像

帝一

有问题私聊我


访客:13998

在线 


活动打卡代码 AcWing 379. 捉迷藏

帝一
3小时前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 210;
bool d[N][N];
int match[N];
bool st[N];

int n, m;

bool find(int x)
{
    for(int i = 1; i <= n; i ++)
        if(d[x][i] && !st[i])
        {
            st[i] = true;
            int k = match[i];
            if(!k || find(k))
            {
                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;
}


活动打卡代码 AcWing 378. 骑士放置

帝一
3小时前
#include <iostream>
#include <cstring>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 110;
PII match[N][N];
bool g[N][N], st[N][N];

int n, m;

int dx[] = {-2, -1, 1, 2, 2, 1, -1, -2}, dy[] = {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(st[a][b] || g[a][b])continue;
        st[a][b] = true;
        PII k = match[a][b];
        if(!k.x || find(k.x, k.y))
        {
            match[a][b] = {x, y};
            return true;
        }
    }
    return false;
}

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


活动打卡代码 AcWing 376. 机器任务

帝一
9小时前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 110, M = 1010;
int h[N], e[M], ne[M], idx;
int n, m, k;
int match[N];
bool st[N];
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

bool find(int u)
{
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(st[j])continue;
        st[j] = true;
        if(match[j] == -1 || find(match[j]))
        {
            match[j] = u;
            return true;
        }
    }
    return false;
}

int main()
{
    while(cin >> n, n)
    {
        idx = 0;
        memset(h, -1, sizeof h);
        memset(match, -1, sizeof match);
        cin >> m >> k;
        while(k --)
        {
            int t, a, b;
            cin >> t >> a >> b;
            if(!a || !b)continue;
            add(a, b);
        }
        int res = 0;
        for(int i = 0; i < n; i ++)
        {
            memset(st, 0, sizeof st);
            if(find(i))res ++;
        }
        cout << res << endl;
    }
    return 0;
}


活动打卡代码 AcWing 372. 棋盘覆盖

帝一
10小时前
#include <iostream>
#include <cstring>

using namespace std;
typedef pair<int, int> PII;
const int N = 110;
PII match[N][N];
bool st[N][N], g[N][N];
int n, m;
int dx[] = {-1, 0, 1, 0}, dy[] = {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 < 1 || a > n || b < 1 || b > n)continue;
        if(st[a][b] || g[a][b])continue;
        st[a][b] = true;
        PII k = match[a][b];
        if(k.first == -1 || find(k.first, k.second)){
            match[a][b] = {x, y};
        return true;
        }
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    while(m --)
    {
        int a, b;
        cin >> a >> b;
        g[a][b] = 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;
}


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

帝一
11小时前
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

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, ne[idx] = h[a], w[idx] = c, 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] && color[j] == color[u])return false;
        if(!color[j])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()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);
    while(m --)
    {
        int a, b, c;
        scanf("%d%d%d", &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;
    }
    printf("%d\n", r);
    return 0;
}



帝一
23小时前

无向图的割边判断法则

首先无向图中不存在横叉边
subtree(i): 以i为根节点的子树。 dfn[x] : x节点的时间戳。 low[y]:表示y的追溯值
无向图(x, y)为桥,当且仅当搜索树上存在x的一个子节点满足:
dfn[x] < low[y],那么y无论如何走走不到x或者x的祖宗节点,那么把这条边删了,相当于形成了两个封闭环境,那么(x,y)就是割边即桥。
由于是无向图因此如果是从x到y的边,那么就不能用从y到x的边来更新low[y],但是如果 存在重边的话因为这两点可以通过不同的路径到达,那么就可以用dfn[x]来更新low[y];

void tarjan(int u, int in_edge) // in_edge为u的父节点到u的边的编号 
{
    dfn[u] = low[u] = ++ timestamp; // 时间戳

    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]) //满足割边要求
            {
                in_bridge[i] = in_bridge[i ^ 1] = true; //因为是双向边,两条边都标记一下
            }
        }
        else if(i != in_dege^1)low[u] = min(low[u], dfn[j]); // 如果这条边不是父节点到子节点的逆边
    }
}

割点的判断法则
若x不是搜索树的根节点(深度优先遍历的起点),则x是割带你当且仅当搜索树上存在x的一个子节点y满足
dfn[x] <= low[y];
若x是搜索树的根节点,则当且仅当搜索树上存在至少两个点y1, y2满足上述条件。
这里由于去等号了,所以不需要在判断父节点和重边问题。

void tarjan(int u)
{
    dfn[u] = low[u] = ++timestamp; // 时间戳
    int cnt = 0; // 判断u节点 存在几个满足上述的子节点
    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)in_val[u] = true; // 如果u不是根节点或者满足条件的子节点大于1 了标记
            }
        }
        else low[u] = min(low[u], dfn[j]); //跟新low[u]
    }
}

无向图的双联通分量
包括边的双联通分量e-DCC和点的双联通分量v-DCC
- 点的双联通分量满足条件
1图中的定点数不超过2
2图中任意两点都同时包含在至少一个简单环中。简单环就是不自交的环。
- 边的双联通分量满足条件
1 当且仅当任意一条边都包含在至少一个环中
e-DCC求法
先用tarjan算法标记所有的桥边,再做一遍dfs,遍历过程中不访问桥边,划分出每个联通块.
id[x] 表示节点x所属的e-DCC编号

void dfs(int u)
{
    id[x] = dcc_cnt; // 节点编号
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(id[j] || in_bridge[j])continue; // 如果子节点已经被遍历过或者说子节点和父节点之间的边为桥
        dfs(j);
    }
}

e-DCC缩点操作
把每个e-DCC看成一个点,把桥边(x, y) 当成id[x] 与 id[y] 的无向边,会产生一棵树(若原图为非联通图,则产生生成森林)。

for(int i = 0; i < idx; i ++)//枚举每条边
{
    int a = e[i ^ 1], b = e[i];//把连接边的两个节点编号抠出来
    if(id[a] == id[b]) continue;//判断两个点是否属于同一个e-DCC,属于的话pass
    add(a, b);// 把两个节点练一条边。
}

点的双连通分量v-dcc的求法
首先要明确一点,每个割点至少存在与两个或两个以上的v-dcc中
除了孤立点外,v-dcc分量的大小至少为2
如何找出所有的v-dcc
1) 当一个节点第一次被访问时,把该节点入栈
2)当判定割点的条件dfn[x] <= low[y] 成立时,无论x是否为根,都要
1.从栈顶不断弹出节点,知道节点y弹出。
2 要把刚刚弹出的所有点与割点x一起 组成一个v-dcc

void tarjan(int u)
{
    dfn[u] = low[u] = ++ timestamp; // 时间戳
    stk[++ top] = u; // 把当前点放到栈中
    if(u == root && h[u] == -1) //如果为孤立点单独处理
    {
        ++ dcc_cnt; // v-dcc编号
        dcc[dcc_cnt].push_back(u);
        return ;
    }
    int cnt = 0; // 割点下面有几个v-dcc
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = ne[i];
        if(!df[j])//没有遍历过的话
        {
            tarjan(j);
            low[u] = min(low[u], low[j]); // 更新low[u]
            if(dfn[u] <= low[j]) //符合割点判断条件
            {
                ++ cnt;
                if(u != root || cnt > 1) cnt[u] = true; // 如果是割点那么标记一下
                int y;
                ++ dcc_cnt; // v-dcc编号
                do 
                {
                    y = stk[top --];// v-dcc的成员节点
                    dcc[dcc_cnt].push_back(y);
                }while(y != j);
                dcc[dcc_cnt].push_back(u);
            }
            else low[u] = min(low[u], dfn[j]); // 最后把x要放到v-dcc中
        }
    }
}

v-dcc的缩点
v-dcc的建图和e_dcc、scc不太一样
由于一个割点可能属于多个v-dcc,设图中有p个割点和t个v-dcc。建图的话就是用每个v-dcc的编号向它所包含的每个割点连一条无向边,因此节点数目可能为2*N个。

for(int i = 1; i <= n; i ++)
    if(cnt[i])new[i] = ++ idx; // 先把每个割点赋予一个新的编号
for(int i = 1; i <= dcc_cnt; i ++)// 枚举每一个v-dcc如果存在割点就向割点的新编连一条无向边
    for(int j = 0; j < dcc[i].size(); j ++)
    {
        int k = dcc[i][j];
        if(cnt[k])add(i, new[k]), add(new[k], i); 
    }

总结:强联通分量缩点后变成拓扑图。
双联通分量缩点后变成树。
一个点即是e-dcc也是v-dcc
两个点是v-dcc但不是e-dcc




帝一
23小时前

算法思路

枚举由于图可能是非联通图因此要枚举每个连通块。设sum 为建立的出口数量, res为方案数
sum = 每个连通块的数量之和, res = 每个连通块的方案之积 (基于乘法原理)
1)如果v_dcc中不存在割点,那么只需要建立两条出口 假设连通块是数量为cnt,sum += 2, res = cnt * (cnt - 1) / 2;
但是如果连通块只有一个点的话需要特判sum , res不变
2) 如果v-dcc中只存在一个割点,那么sum
, res *= cnt - 1;
3) 如果v-dcc中存在两个或者两个以上的割点,那么不需要设立点。



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

帝一
1天前
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>

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], timestamp;
int stk[N], top;
bool cut[N];
int dcc_cnt;
vector<int> dcc[N];
int m;
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(root == u && h[u] == -1)
    {
        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(root != u || 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 = 0;
    while(cin >> m, m)
    {
        for (int i = 1; i <= dcc_cnt; i ++ ) dcc[i].clear();
        memset(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        top = idx = timestamp = dcc_cnt = 0;
        memset(cut, 0, sizeof cut);
        int maxv = 0;
        while(m --)
        {
            int a, b;
            cin >>  a >> b;
            add(a, b), add(b, a);
            maxv = max(maxv, max(a, b));
        }
        for(root  = 1; root <= maxv; root ++)
            if(!dfn[root])
                tarjan(root);
        ULL res = 1;
        int sum = 0;
        for(int i = 1; i <= dcc_cnt; i ++){
            int cnt = 0;
            for(int j = 0; j < dcc[i].size(); j ++)
            {
                int k = dcc[i][j];
                if(cut[k]) cnt ++;
            }
            if(!cnt){
                if(dcc[i].size() > 1)sum += 2, res *= dcc[i].size() * (dcc[i].size() - 1) / 2;
                else sum ++;
            }
            else if(cnt == 1)sum ++, res *= dcc[i].size() - 1;
        }
        printf("Case %d: %d %llu\n", ++ T, sum, res);
    }
    return 0;
}



帝一
1天前

算法思路

根据题意 就是求删除图中的一个点使得图中的连通块数目最大,并求出这个最大值。
如果这个图是一个树的话啊,那么可以用dfs求解O(N)但是是一个图可能存在环用dfs会相当麻烦,因此利用割点来求会方便很多。对于整个图来说假如有cnt个连通块,如果一个连通块i不存在割点,那么最大值就是cnt + 1, 如果连通块存在割点,那么最大值就是cnt - 1 + x(删除割点剩余的连通块数目 + x本身算一个点);

void tarjon(int u)
{
    dfn[u] = low[u] = ++ timestamp; //时间戳
    int cnt = 0; // 记录u下面有几个连通块
    for(int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if(!dfn[j])
        {
            tarjon(j);
            low[u] = min(low[u], low[j]);
            if(dfn[u] <= low[j])cnt ++; //如果满足条件那么u是割点,记录u下面连接几个连通块
        }
        else low[u] = min(low[u], dfn[j]); // 更新low[u];
    }
    if(root != u)cnt ++; // 如果u不是根节点 再把u的父节点的连通块加上
    ans = max(ans, cnt); // 最后取一个最大值
} 


活动打卡代码 AcWing 1183. 电力

帝一
1天前
#include <iostream>
#include <cstring>

using namespace std;
const int N = 10010, M = 30010;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int size[N];
int n, m;
int ans = 0;
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;
    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 ++;
        }
        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(h, -1, sizeof h);
        memset(dfn, 0, sizeof dfn);
        memset(low, 0, sizeof low);
        timestamp = 0;
        idx = 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;
}