标签 graphs 下的文章

D. Mouse Hunt

题目链接

Educational Codeforces Round 49 (Rated for Div. 2)--D. Mouse Hunt

题解

中档题,题意大概是一只老鼠与一群房间,每个房间老鼠会往某个特定的房间跑,求最少的可以抓到老鼠的陷阱费用。
枚举每个最终的环即可。

代码

#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 50;

int dfn[maxn], low[maxn], scccnt = 0, sccindex = 0, belong[maxn];

bool instack[maxn];
stack<int>sta;
vector<int>G[maxn];

void tarjan(int v) {
    dfn[v] = low[v] = ++sccindex;
    sta.push(v); instack[v] = true; int j;
    for (auto i = G[v].begin(); i != G[v].end(); i++) {
        int j = *i;
        if (!dfn[j]) {
            tarjan(j);
            low[v] = min(low[v], low[j]);
        }
        else if (instack[j] && dfn[j]<low[v])
            low[v] = dfn[j];
    }
    if (low[v] == dfn[v]) {
        scccnt++;
        do {
            j = sta.top(); instack[j] = false;
            sta.pop(); belong[j] = scccnt;
        } while (j != v);
    }
}

int outdegree[maxn], c[maxn];
int minn[maxn], size1[maxn];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n, i, j, k;
    cin >> n;
    for (i = 1; i <= n; i++)cin >> c[i];
    long long ans = 0;
    for (i = 1; i <= n; i++) {
        cin >> j;
        G[i].push_back(j); outdegree[i]++;
        if (j == i)ans += c[i];
    }
    for (i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);

    for (i = 1; i <= n; i++)
        size1[belong[i]]++;
    memset(minn, 0x3f, sizeof(minn));
    for (i = 1; i <= n; i++) {
        if (size1[belong[i]] <= 1)continue;
        minn[belong[i]] = min(minn[belong[i]], c[i]);
    }
    for (i = 1; i <= n; i++) {
        if (minn[i] != 0x3f3f3f3f)
            ans += minn[i];
    }
    cout << ans << endl;

    return 0;
}

B. Ant Man

题目链接

Codeforces Round #366 (Div. 1)--B. Ant Man

题解

中档题。题意大概是给定一堆数据,经过一系列复杂的操作后可以转化为两两之间的费用,指定起点终点,要求在遍历每个节点的情况下费用最小。
首先将路径指定为起点至终点,之后依次插入节点贪心,在已有路径上找到某一位置插入使得费用增加的最少,将所有点插入后即为最优解。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int MAXN = 5e3 + 5;
const int MOD = 1e9 + 7;
const int inf = (1 << 31) - 1;
const ll INF = 1ll << 60;



ll n, s, e;
ll q1, q2, q3, q4, q5;
ll x[MAXN], a[MAXN], b[MAXN], c[MAXN], d[MAXN];
ll cost[MAXN][MAXN];
ll Next[MAXN];

inline ll jump(int i, int j) {
    return  abs(x[i] - x[j]) + (i > j ? (c[i] + b[j]) : (d[i] + a[j]));
}

inline void update(int num) {
    q1 = s;
    q4 = INF;
    while (Next[q1] != 0) {
        if (-cost[q1][Next[q1]] + cost[q1][num] + cost[num][Next[q1]] < q4) {
            q2 = q1;
            q4 = -cost[q1][Next[q1]] + cost[q1][num] + cost[num][Next[q1]];
        }
        q1 = Next[q1];
    }
}

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

    cin >> n >> s >> e;
    for (int i = 1; i <= n; i++) cin >> x[i];
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];
    for (int i = 1; i <= n; i++) cin >> c[i];
    for (int i = 1; i <= n; i++) cin >> d[i];
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            cost[i][j] = jump(i, j);
            cost[j][i] = jump(j, i);
        }
    }
    Next[s] = e;
    for (int j = 1; j <= n; j++) {
        if (!Next[j] && j != e) {
            update(j);
            Next[j] = Next[q2];
            Next[q2] = j;
        }
    }
    ll ans(0);
    q1 = s;
    while (Next[q1]) {
        ans += cost[q1][Next[q1]];
        q1 = Next[q1];
    }
    cout << ans << endl;
}

F. Mars rover

题目链接

Codeforces Round #499 (Div. 2)--F. Mars rover

题解

高档题。题意大概是给定一个图,每个节点可能包含 AND (2 inputs), OR (2
inputs), XOR (2 inputs), NOT (1 input) 四种情况,除此之外还有 IN 节点作为输入。所有输入经过一系列逻辑运算后将得到一个输出。现给定这些输入,求改变每个输入节点后输出节点的值。

首先从将每个节点对初始输入的值所表达的值求出来。
之后将输出标记为重要,并从输出节点开始对每个节点标记,标记规则如下:

  • 如果该节点为不重要,则它的输入节点均为不重要
  • 如果该节点为重要,若改变某一输入节点的值该节点的值改变,则这一输入节点为重要,否则这一输入节点为不重要。

最后判断每个输入节点是否为重要节点,如果是则输出输出节点原本的值的否,如果不是则输出输出节点原本的值。

一定要注意逻辑运算符的优先级,我被这个坑了几十分钟。

代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
using namespace std;

int n, k, q1;
struct MyStruct
{
    bool self, isimportant;
    int in1, in2;
    int type;//and=0,or=1,xor=2,not=3,in=4
} a[1000005];
char s[5];
vector<int>inputs;

void pd(int i) {
    if (a[i].type == 4)return;
    if (a[i].isimportant == false) {
        a[a[i].in1].isimportant = false;
        pd(a[i].in1);
        if (a[i].type != 3) {
            a[a[i].in2].isimportant = false;
            pd(a[i].in2);
        }
    }
    else {
        if (a[i].type == 0) {
            if (((!a[a[i].in1].self)&(a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self)&(a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 1) {
            if (((!a[a[i].in1].self) | (a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self) | (a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 2) {
            if (((!a[a[i].in1].self) xor (a[a[i].in2].self)) != a[i].self) {
                a[a[i].in1].isimportant = true;
                pd(a[i].in1);
            }
            else {
                a[a[i].in1].isimportant = false;
                pd(a[i].in1);
            }
            if (((!a[a[i].in2].self) xor (a[a[i].in1].self)) != a[i].self) {
                a[a[i].in2].isimportant = true;
                pd(a[i].in2);
            }
            else {
                a[a[i].in2].isimportant = false;
                pd(a[i].in2);
            }
        }
        else if (a[i].type == 3) {
            a[a[i].in1].isimportant = true;
            pd(a[i].in1);
        }
    }
}



bool fill(int i) {
    switch (a[i].type) {
    case 4:
        return a[i].self;
    case 0:
        a[i].self = fill(a[i].in1) & fill(a[i].in2);
        return a[i].self;
    case 1:
        a[i].self = fill(a[i].in1) | fill(a[i].in2);
        return a[i].self;
    case 2:
        a[i].self = fill(a[i].in1) xor fill(a[i].in2);
        return a[i].self;
    case 3:
        a[i].self = !fill(a[i].in1);
        return a[i].self;
    }
}

int main() {
    memset(a, 0, sizeof(a));
    cin >> n;
    for (int i = 1; i <= n; i++) {
        scanf("%s", &s);
        if (s[0] == 'A') {
            a[i].type = 0;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'O') {
            a[i].type = 1;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'X') {
            a[i].type = 2;
            scanf("%d %d", &a[i].in1, &a[i].in2);
        }
        else if (s[0] == 'N') {
            a[i].type = 3;
            scanf("%d", &a[i].in1);
        }
        else if (s[0] == 'I') {
            a[i].type = 4;
            scanf("%d", &a[i].in1);
            a[i].self = a[i].in1;
            inputs.push_back(i);
        }
    }

    fill(1);
    a[1].isimportant = true;
    pd(1);

    for (auto i : inputs) {
        if (a[i].isimportant) printf("%d", !a[1].self);
        else printf("%d", a[1].self);
    }
}

D. Relatively Prime Graph

题目链接

Educational Codeforces Round 47 (Rated for Div. 2)--D. Relatively Prime Graph

题解

中档题。题意大概是要求构成n个点m条边个图。图要求满足联通,每个边连接的两个点最大公约数为1,没有重边自环。
如果m<n-1图不联通,否则直接两重循环判断如果最大公约数为1则连接两点。

代码

#include <iostream>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
using namespace std;
int gcd(int a, int b) {
    return b ? gcd(b, a%b) : a;
}
vector <pair<int, int>> v;
int n, m;
int main() {
    cin >> n >> m;
    if (m < n - 1) { 
        cout << "Impossible"; 
        return 0;
    }
    for (int i = 1; i < n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (gcd(i, j) == 1)v.push_back({ i,j });
            if (v.size() == m) {
                cout << "Possible" << endl;
                for (auto k : v) {
                    cout << k.first << ' ' << k.second << endl;
                }
                return 0;
            }
        }
    }
    cout << "Impossible";
}

C. A Mist of Florescence

题目链接

Codeforces Round #??487(Div. 2)--C. A Mist of Florescence

题解

简单题/难题(也可能是傻逼题)。题意大概是使用四种颜色对一块区域染色,使每种颜色的联通块的数量为所要求的数量。
乍一看好像很麻烦的样子,实际上注意到数据规模,每种颜色的联通块的数量至少为1,至多为100,而允许的区域数量有50*500,那就可以玄学AC了。首先对四种颜色各染一大块,然后往第一种颜色里填充第二种颜色,第二种颜色里填充第三种颜色,以此类推直到符合要求即可。

代码

#include <cstdio>
#include <cmath>
#include <iostream>
#include <string.h>
#include <string>
using namespace std;
char s[55][55];
int a, b, c, d;
int main() {
    cin >> a >> b >> c >> d;
    a--;
    b--;
    c--;
    d--;
    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            if (i / 12 == 0) s[i][j] = 'A';
            else if (i / 12 == 1) s[i][j] = 'B';
            else if (i / 12 == 2) s[i][j] = 'C';
            else s[i][j] = 'D';
        }
    }
    int temp = 0;
    for (int i = 1; i <= 10; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!d)break;
            temp++;
            if (temp % 2) { s[i][j] = 'D'; d--; }
        }
    }
    temp = 0;
    for (int i = 13; i <= 22; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!a)break;
            temp++;
            if (temp % 2) { s[i][j] = 'A'; a--; }
        }
    }
    temp = 0;
    for (int i = 25; i <= 37; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!b)break;
            temp++;
            if (temp % 2) { s[i][j] = 'B'; b--; }
        }
    }
    temp = 0;
    for (int i = 37; i <= 47; i+=2) {
        for (int j = 1; j < 49; j++) {
            if (!c)break;
            temp++;
            if (temp % 2) { s[i][j] = 'C'; c--; }
        }
    }
    cout << 50 << ' ' << 50 << endl;
    for (int i = 0; i < 50; i++) {
        cout << s[i] << endl;
    }
}

C. Cut 'em all!

题目链接

Codeforces Round #484 (Div. 2)--C. Cut 'em all!

题解

中档题,题意大概是给定一个树,求最多可以删去多少条边满足剩下的每个联通分量均为偶数个节点。
emmm说实话我没想到什么特别的方法于是从叶子节点开始暴力……

代码

#include <bits/stdc++.h>
using namespace std;
int n,q,w;
map<int,int> a[100002];
bool boo[100002];
int link[100002][2];
map<int,map<int,int>> linknum;
int find(int from,int to){
    if (linknum[from][to]!=0)return linknum[from][to];
    if (a[to][0]==1)return 1;
    else {
        int num=1;
        for (int i=1;i<=a[to][0];i++){
            if (a[to][i]!=from)num+=find(to,a[to][i]);
        }
        linknum[from][to]=num;
        linknum[to][from]=num;
        return num;
    }
}
int main() {
    cin>>n;
    if (n%2==1){
        cout<<-1;
        return 0;
    }
    for (int i=1;i<=n-1;i++){
        cin>>q>>w;
        link[i][0]=q;
        link[i][1]=w;
        a[q][0]++;
        a[w][0]++;
        a[q][a[q][0]]=w;
        a[w][a[w][0]]=q;
    }
    int ans=0;
    int cache;
    for (int i=1;i<=n-1;i++){
        if (a[link[i][0]][0]==1||a[link[i][1]][0]==1)continue;
        else {
            if (find(link[i][0],link[i][1])%2==0)
            ans++;
            //cout<<link[i][0]<<' '<<link[i][1]<<endl;
        }
    }
    cout<<ans;
}

E. Cyclic Components

time limit per test:2 seconds

memory limit per test:256 megabytes

input:standard input

output:standard output

You are given an undirected graph consisting of n vertices and m edges. Your task is to find the number of connected components which are cycles.

Here are some definitions of graph theory.

An undirected graph consists of two sets: set of nodes (called vertices) and set of edges. Each edge connects a pair of vertices. All edges are bidirectional (i.e. if a vertex a is connected with a vertex b, a vertex b is also connected with a vertex a). An edge can't connect vertex with itself, there is at most one edge between a pair of vertices.

Two vertices u and v belong to the same connected component if and only if there is at least one path along edges connecting u and v.

A connected component is a cycle if and only if its vertices can be reordered in such a way that:

  • the first vertex is connected with the second vertex by an edge,
  • the second vertex is connected with the third vertex by an edge,
  • ...
  • the last vertex is connected with the first vertex by an edge,
  • all the described edges of a cycle are distinct.

A cycle doesn't contain any other edges except described above. By definition any cycle contains three or more vertices.

6b053ff1e4d04b1dc6db0b6c434db1316c2325ef.png

There are 6 connected components, 2 of them are cycles: [7,10,16] and [5,11,9,15].

- 阅读剩余部分 -