头像

Protein

OIer




离线:2天前


最近来访(278)
用户头像
skydegree
用户头像
......_519
用户头像
诗人kris
用户头像
头戴凤翅紫金冠身披锁子黄金甲足蹬藕丝步云履手持如意金箍棒之煞
用户头像
wzc0926
用户头像
青莲.
用户头像
徐一凯
用户头像
DarksideCoder
用户头像
空白_9
用户头像
鼠鼠今天吃嘉然
用户头像
invisible-pat.
用户头像
龚子昂
用户头像
SunRayGold
用户头像
九峰
用户头像
不见落木
用户头像
Spaceforest
用户头像
liuxiaocs
用户头像
xxxuan
用户头像
Rudas
用户头像
我是sun

活动打卡代码 AcWing 383. 观光

Protein
3天前
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 1010, M = 20010;
struct VER { int id, type, dist; };
bool operator>(VER a, VER b) { return a.dist > b.dist; }
int n, m, S, T;
int h[N], e[M], w[M], ne[M], idx;
int dist[N][2], cnt[N][2];
bool st[N][2];
void add(int a, int b, int c){
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra(){   
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    dist[S][0] = 0, cnt[S][0] = 1;
    priority_queue<VER, vector<VER>, greater<VER>> heap;
    heap.push({S, 0, 0});
    while (heap.size()){
        VER t = heap.top();
        heap.pop();
        int ver = t.id, type = t.type, distance = t.dist, count = cnt[ver][type];
        if (st[ver][type]) continue;
        st[ver][type] = true;
        for (int i = h[ver]; ~i; i = ne[i]){
            int j = e[i];
            if (dist[j][0] > distance + w[i]){
                dist[j][1] = dist[j][0], cnt[j][1] = cnt[j][0];
                heap.push({j, 1, dist[j][1]});
                dist[j][0] = distance + w[i], cnt[j][0] = count;
                heap.push({j, 0, dist[j][0]});
            }
            else if (dist[j][0] == distance + w[i]) cnt[j][0] += count;
            else if (dist[j][1] > distance + w[i]){
                dist[j][1] = distance + w[i], cnt[j][1] = count;
                heap.push({j, 1, dist[j][1]});
            }
            else if (dist[j][1] == distance + w[i]) cnt[j][1] += count;
        }
    }
    int res = cnt[T][0];
    if (dist[T][0] + 1 == dist[T][1]) res += cnt[T][1];
    return res;
}
int main(){
    int cases;
    scanf("%d", &cases);
    while (cases -- ){
        scanf("%d%d", &n, &m);
        memset(h, -1, sizeof h);
        idx = 0;
        while (m -- ){
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            add(a, b, c);
        }
        scanf("%d%d", &S, &T);
        printf("%d\n", dijkstra());
    }
    return 0;
}


活动打卡代码 AcWing 380. 舞动的夜晚

Protein
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 20010, M = 400010, INF = 1e9;
int n, m, t, S, T;
int h[N], pt[M], to[M], f[M], idx;
void add(int a, int b, int c) {
    f[idx] = c, to[idx] = b, pt[idx] = h[a], h[a] = idx++;
    f[idx] = 0, to[idx] = a, pt[idx] = h[b], h[b] = idx++;
}
int d[N], cur[N], q[N];
bool BFS() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[S] = 0, q[++tt] = S, cur[S] = h[S];
    for (int u; u = q[hh], hh <= tt; hh++)
        for (int i = h[u], v; v = to[i], ~i; i = pt[i]) {
            if (d[v] != -1 || !f[i]) continue;
            d[v] = d[u] + 1, cur[v] = h[v], q[++tt] = v;
            if (v == T) return true;
        }
    return false;
}
int DFS(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u], v; v = to[i], ~i && flow < lim; cur[u] = i, i = pt[i]) {
        if (d[v] != d[u] + 1 || !f[i]) continue;
        int t = DFS(v, min(f[i], lim - flow));
        if (!t) d[v] = -1;
        f[i] -= t, f[i ^ 1] += t, flow += t;
    }
    return flow;
}
int Dinic() {
    int res = 0, flow;
    while (BFS()) while (flow = DFS(S, INF)) res += flow;
    return res;
}
vector<int> R;
int dfn[N], low[N], stk[N], ins[N], c[N], cnt, top, ts;
void Tarjan(int u) {
    dfn[u] = low[u] = ++ts, stk[++top] = u, ins[u] = 1;
    for (int i = h[u], v; v = to[i], ~i; i = pt[i])
        if (!f[i]) continue;
        else if (!dfn[v]) Tarjan(v), low[u] = min(low[u], low[v]);
        else if (ins[v]) low[u] = min(low[u], dfn[v]);
    if (dfn[u] != low[u]) return;
    cnt++; int t;
    do c[t = stk[top--]] = cnt, ins[t] = 0; while (t != u);
}
int main() {
    cin >> n >> m >> t, S = n + m + 1, T = S + 1;
    memset(h, -1, sizeof h);
    for (int i = 1, a, b; i <= t; i++)
        cin >> a >> b, add(a, b + n, 1);
    for (int i = 1; i <= n; i++) add(S, i, 1);
    for (int i = 1; i <= m; i++) add(i + n, T, 1);
    Dinic();
    for (int i = 1; i <= n + m + 2; i++) 
        if (!dfn[i]) Tarjan(i);
    int res = 0;
    for (int i = 0; i < t * 2; i += 2)
        if (f[i] && c[to[i ^ 1]] != c[to[i]])
            res++, R.push_back((i / 2) + 1);
    cout << res << endl;
    for (auto x : R) cout << x << ' ';
    return cout << endl, 0;
}


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

Protein
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 510, M = N * N, INF = 2e9;
int n, m, S, T, G[N][N];
int h[N], pt[M], to[M], f[M], idx;
void add(int a, int b, int c) {
    f[idx] = c, to[idx] = b, pt[idx] = h[a], h[a] = idx++;
    f[idx] = 0, to[idx] = a, pt[idx] = h[b], h[b] = idx++;
}
int d[N], cur[N], q[N];
bool BFS() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[S] = 0, q[++tt] = S, cur[S] = h[S];
    for (int u; u = q[hh], hh <= tt; hh++)
        for (int i = h[u], v; v = to[i], ~i; i = pt[i]) {
            if (d[v] != -1 || !f[i]) continue;
            d[v] = d[u] + 1, cur[v] = h[v], q[++tt] = v;
            if (v == T) return true;
        }
    return false;
}
int DFS(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u], v; v = to[i], ~i && flow < lim; cur[u] = i, i = pt[i]) {
        if (d[v] != d[u] + 1 || !f[i]) continue;
        int t = DFS(v, min(f[i], lim - flow));
        if (!t) d[v] = -1;
        f[i] -= t, f[i ^ 1] += t, flow += t;
    }
    return flow;
}
int Dinic() {
    int res = 0, flow;
    while (BFS()) while (flow = DFS(S, INF)) res += flow;
    return res;
}
int main() {
    cin >> n >> m, memset(h, -1, sizeof h);
    S = n * 2 + 1, T = S + 1;
    for (int i = 1, a, b; i <= m; i++)
        cin >> a >> b, G[a][b] = 1;
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                G[i][j] |= G[i][k] & G[k][j];
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (G[i][j]) add(i, j + n, 1);
    for (int i = 1; i <= n; i++) add(S, i, 1);
    for (int i = 1; i <= n; i++) add(i + n, T, 1);
    cout << n - Dinic() << endl;
}


活动打卡代码 AcWing 377. 泥泞的区域

Protein
4天前
#include <iostream>
#include <algorithm>.
#include <cstring>
using namespace std;
const int N = 2510, M = N * N, INF = 1e9;
int n, m, S, T;
int h[N], pt[M], to[M], f[M], idx;
void add(int a, int b, int c) {
    f[idx] = c, to[idx] = b, pt[idx] = h[a], h[a] = idx++;
    f[idx] = 0, to[idx] = a, pt[idx] = h[b], h[b] = idx++;
}
int d[N], cur[N], q[N];
bool BFS() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[S] = 0, q[++tt] = S, cur[S] = h[S];
    for (int u; u = q[hh], hh <= tt; hh++)
        for (int i = h[u], v; v = to[i], ~i; i = pt[i]) {
            if (d[v] != -1 || !f[i]) continue;
            d[v] = d[u] + 1, cur[v] = h[v], q[++tt] = v;
            if (v == T) return true;
        }
    return false;
}
int DFS(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u], v; v = to[i], ~i && flow < lim; cur[u] = i, i = pt[i]) {
        if (d[v] != d[u] + 1 || !f[i]) continue;
        int t = DFS(v, min(f[i], lim - flow));
        if (!t) d[v] = -1;
        f[i] -= t, f[i ^ 1] += t, flow += t;
    }
    return flow;
}
int Dinic() {
    int res = 0, flow;
    while (BFS()) while (flow = DFS(S, INF)) res += flow;
    return res;
}
char G[N][N]; int rid[N][N], cid[N][N];
int main() {
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);
    for (int i = 1; i <= n; i++) scanf("%s", G[i] + 1);
    int cnt1 = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1, f = 0; j <= m; j++)
            if (G[i][j] != '*') cnt1 += f, f = 0;
            else rid[i][j] = cnt1, f = 1, cnt1 += (j == m);   
    int cnt2 = cnt1;
    for (int j = 1; j <= m; j++)
        for (int i = 1, f = 0; i <= n; i++)
            if (G[i][j] != '*') cnt2 += f, f = 0;
            else cid[i][j] = cnt2, f = 1, cnt2 += (i == n);
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= m; j++)
            if (G[i][j] == '*') add(rid[i][j], cid[i][j], 1);
    S = cnt2, T = S + 1;
    for (int i = 1; i <= cnt1 - 1; i++) add(S, i, 1);
    for (int i = cnt1; i <= cnt2 - 1; i++) add(i, T, 1);
    cout << Dinic() << endl;
    return 0;
}


活动打卡代码 AcWing 382. K取方格数

Protein
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 5010, M = 20010, INF = 1e9;
int n, k, S, T;
int h[N], ptr[M], val[M], f[M], w[M], idx;
int q[N], d[N], pre[N], incf[N];
bool st[N];
void add(int a, int b, int c, int d) {
    val[idx] = b, f[idx] = c, w[idx] = d, ptr[idx] = h[a], h[a] = idx++;
    val[idx] = a, f[idx] = 0, w[idx] = -d, ptr[idx] = h[b], h[b] = idx++;
}
int get(int x, int y, int t) {
    return (x * n + y) * 2 + t;
}
bool SPFA() {
    int hh = 0, tt = 1;
    memset(d, -0x3f, sizeof d);
    memset(incf, 0, sizeof incf);
    q[0] = S, d[S] = 0, incf[S] = INF;
    while (hh != tt) {
        int t = q[hh++];
        if (hh == N) hh = 0;
        st[t] = false;
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (f[i] && d[ver] < d[t] + w[i]) {
                d[ver] = d[t] + w[i];
                pre[ver] = i, incf[ver] = min(f[i], incf[t]);
                if (!st[ver]) {
                    q[tt++] = ver;
                    if (tt == N) tt = 0;
                    st[ver] = true;
                }
            }
        }
    }
    return incf[T] > 0;
}
int EK() {
    int cost = 0;
    while (SPFA()) {
        int t = incf[T];
        cost += t * d[T];
        for (int i = T; i != S; i = val[pre[i] ^ 1]) 
            f[pre[i]] -= t, f[pre[i] ^ 1] += t;
    }
    return cost;
}
int main() {
    cin >> n >> k;
    S = n * n * 2, T = n * n * 2 + 1;
    memset(h, -1, sizeof h);
    add(S, get(0, 0, 0), k, 0);
    add(get(n - 1, n - 1, 1), T, k, 0);
    for (int i = 0; i < n; i++) 
        for (int j = 0, c; j < n && cin >> c; j++) {
            add(get(i, j, 0), get(i, j, 1), 1, c);
            add(get(i, j, 0), get(i, j, 1), INF, 0);
            if (i + 1 < n) add(get(i, j, 1), get(i + 1, j, 0), INF, 0);
            if (j + 1 < n) add(get(i, j, 1), get(i, j + 1, 0), INF, 0);
        }
    cout << EK() << endl;
    return 0;
}


活动打卡代码 AcWing 381. 有线电视网络

Protein
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#define add(a, b, c) (f[idx] = c, val[idx] = b, ptr[idx] = h[a], h[a] = idx++)
using namespace std;
const int N = 110, M = 10010, INF = 1e9;
int n, m, S, T;
int h[N], val[M], ptr[M], f[M], idx;
int q[N], d[N], cur[N];
bool BFS() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    q[++tt] = S, d[S] = 0, cur[S] = h[S];
    while (hh <= tt) {
        int t = q[hh++];
        for (int i = h[t]; i != -1; i = ptr[i]) {
            int ver = val[i];
            if (d[ver] == -1 && f[i]) {
                d[ver] = d[t] + 1, cur[ver] = h[ver];
                if (ver == T) return true;
                q[++tt] = ver;
            }
        }
    }
    return false;
}
int find(int u, int limit) {
    if (u == T) return limit;
    int flow = 0;
    for (int i = cur[u]; i != -1 && flow < limit; i = ptr[i]) {
        cur[u] = i;
        int ver = val[i];
        if (d[ver] == d[u] + 1 && f[i]) {
            int t = find(ver, min(f[i], limit - flow));
            if (!t) d[ver] = -1;
            f[i] -= t, f[i ^ 1] += t, flow += t;
        }
    }
    return flow;
}
int Dinic() {
    int r = 0, flow;
    while (BFS()) while (flow = find(S, INF)) r += flow;
    return r;
}
int main() {
    while (cin >> n >> m) {
        memset(h, -1, sizeof h), idx = 0;
        for (int i = 0; i < n; i++) add(i, n + i, 1), add(n + i, i, 0);
        for (int a, b; m-- ; ) {
            scanf(" (%d,%d)", &a, &b);
            add(b + n, a, INF), add(a, b + n, 0),
            add(a + n, b, INF), add(b, a + n, 0);
        }
        int res = n;
        for (int i = 0; i < n; i++) 
            for (int j = 0; j < i; j++) {
                S = n + i, T = j;
                for (int k = 0; k < idx; k += 2) 
                    f[k] += f[k ^ 1], f[k ^ 1] = 0;
                res = min(res, Dinic());
            }
        cout << res << endl;
    }
    return 0;
}


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

Protein
4天前
#include<iostream>
#include<cstring>
using namespace std;
typedef pair<int, int>PII;
const int N = 110;
int n, m, t;
int g[N][N], st[N][N];
PII match[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(st[a][b] || g[a][b])continue;
        st[a][b] = true;
        PII t = match[a][b];
        if(t.first == 0 || find(t.first, t.second)){
            match[a][b] = {x, y};
            return true;
        }
    }
    return false;
}
int main(){
    cin >> n >> m >> t;
    for(int i = 0; i < t; 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((i + j) % 2 || g[i][j])continue;
            memset(st, 0, sizeof st);
            if(find(i, j))res++;
        }
    cout << n * m - t - res << endl;
    return 0;
}


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

Protein
4天前
#include<iostream>
#include<cstring>
using namespace std;
const int N = 110;
int n, m, k;
int g[N][N], match[N];
bool st[N];
bool find(int x){
    for(int i = 1; i < m; i++){
        if(!st[i] && g[x][i]){
            st[i] = true;
            int t = match[i];
            if(t == 0 || find(t)){
                match[i] = x;
                return true;
            }
        }
    }
    return false;
}
int main(){
    while(cin >> n, n){
        cin >> m >> k;
        memset(g, 0, sizeof g);
        memset(match, 0, 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 = 1; i < n; i++){
            memset(st, 0, sizeof st);
            if(find(i))res++;
        }
        cout << res << endl;
    }
}



活动打卡代码 AcWing 375. 蚂蚁

Protein
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 210, M = N * N;
int n, m, S, T;
struct PNT { int x, y; } A[N], B[N];
int h[N], pt[M], to[M], f[M], idx;
double wt[M];
void add(int a, int b, int c, double t) {
    wt[idx] = t, f[idx] = c, to[idx] = b, pt[idx] = h[a], h[a] = idx++;
    wt[idx] = -t, f[idx] = 0, to[idx] = a, pt[idx] = h[b], h[b] = idx++;
}
int pre[N], incf[N], st[N], q[N]; double dis[N];
bool BFS() {
    int hh = 0, tt = 0;
    for (int i = 0; i <= n + n + 10; i++) dis[i] = 1e9;
    memset(incf, 0, sizeof incf);
    st[S] = true, q[tt++] = S, dis[S] = 0, incf[S] = 2e9;
    for (int t; st[t = q[hh]] = 0, hh != tt; hh = (hh + 1) % (N - 1))
        for (int i = h[t], v; v = to[i], i != -1; i = pt[i]) {
            if (!f[i] || dis[v] <= dis[t] + wt[i]) continue; 
            dis[v] = dis[t] + wt[i], pre[v] = i;
            incf[v] = min(f[i], incf[t]);
            if (!st[v]) st[q[tt] = v] = 1, tt = (tt + 1) % (N - 1);
        }
    return incf[T] > 0;
}
void EK() {
    int res = 0, cost = 0;
    for (; BFS(); res += incf[T], cost += incf[T] * dis[T])
        for (int i = T; i != S; i = to[pre[i] ^ 1])
            f[pre[i]] -= incf[T], f[pre[i] ^ 1] += incf[T];
}
double sq(double x) { return x * x; }
double dist(PNT a, PNT b) { return sqrt(sq(a.x - b.x) + sq(a.y - b.y)); }
int main() {
    cin >> n, memset(h, -1, sizeof h), S = n + n + 1, T = S + 1;
    for (int i = 1; i <= n; i++) cin >> A[i].x >> A[i].y;
    for (int i = 1; i <= n; i++) cin >> B[i].x >> B[i].y;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) 
            add(i, j + n, 1, dist(A[i], B[j]));
    for (int i = 1; i <= n; i++) add(S, i, 1, 0);
    for (int i = 1; i <= n; i++) add(i + n, T, 1, 0);
    EK();
    for (int i = 1; i <= n; i++)
        for (int j = h[i], v; v = to[j], ~j; j = pt[j])
            if (v != S && f[j] == 0) cout << v - n << endl;
    return 0;
}


活动打卡代码 AcWing 374. 导弹防御塔

Protein
4天前
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
const int N = 100010, M = N << 4, INF = 1e9;
int n, m, S, T;
double T1, T2, V;
struct PNT { double x, y; } D[N], E[N];
int h[N], pt[M], to[M], f[M], idx;
void add(int a, int b, int c) {
    f[idx] = c, to[idx] = b, pt[idx] = h[a], h[a] = idx++;
    f[idx] = 0, to[idx] = a, pt[idx] = h[b], h[b] = idx++;
}
int d[N], cur[N], q[N];
bool BFS() {
    int hh = 0, tt = -1;
    memset(d, -1, sizeof d);
    d[S] = 0, q[++tt] = S, cur[S] = h[S];
    for (int u; u = q[hh], hh <= tt; hh++)
        for (int i = h[u], v; v = to[i], ~i; i = pt[i]) {
            if (d[v] != -1 || !f[i]) continue;
            d[v] = d[u] + 1, cur[v] = h[v], q[++tt] = v;
            if (v == T) return true;
        }
    return false;
}
int DFS(int u, int lim) {
    if (u == T) return lim;
    int flow = 0;
    for (int i = cur[u], v; v = to[i], ~i && flow < lim; cur[u] = i, i = pt[i]) {
        if (d[v] != d[u] + 1 || !f[i]) continue;
        int t = DFS(v, min(f[i], lim - flow));
        if (!t) d[v] = -1;
        f[i] -= t, f[i ^ 1] += t, flow += t;
    }
    return flow;
}
int Dinic() {
    int res = 0, flow;
    while (BFS()) while (flow = DFS(S, INF)) res += flow;
    return res;
}
double sq(double x) { return x * x; }
double dis(PNT a, PNT b) { return sqrt(sq(a.x - b.x) + sq(a.y - b.y)); }
bool check(double mid) {
    int p = min(m, (int)((mid >= T1) + (mid - T1) / (T1 + T2)));
    memset(h, -1, sizeof h), idx = 0, S = m + n * p + 1, T = S + 1;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= p; j++)
            for (int k = 1; k <= m; k++)
                if ((j - 1) * (T1 + T2) + T1 + dis(D[i], E[k]) / V <= mid)
                    add((i - 1) * p + j, k + n * p, 1);
    for (int i = 1; i <= n * p; i++) add(S, i, 1);
    for (int j = 1; j <= m; j++) add(j + n * p, T, 1);
    return Dinic() == m;
}
int main() {
    scanf("%d%d%lf%lf%lf", &n, &m, &T1, &T2, &V), T1 /= 60;
    for (int i = 1; i <= m; i++) scanf("%lf%lf", &E[i].x, &E[i].y);
    for (int i = 1; i <= n; i++) scanf("%lf%lf", &D[i].x, &D[i].y);
    double l = 0, r = 1e9;
    for (double mid; mid = (l + r) / 2, r - l > 1e-8; )
        check(mid) ? r = mid : l = mid;
    return printf("%.6lf", l), 0;
}