匈牙利算法

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

using namespace std;

#define x first
#define y second

typedef pair<int, int> PII;

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

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) & 1 && !g[i][j]) {
                memset(st, 0, sizeof st);
                if (find(i, j)) res ++;
            }

    cout << res << endl;

    return 0;
}

染色法

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

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 x, int c, int mid) {
    color[x] = c;

    for (int i = h[x]; ~i; i = ne[i]) {
        if (w[i] <= mid) continue;//y这个节点可能多个，所以，必须放这
        int y = e[i];
        if (color[y]) {//如果当前点染过色了
            if (color[y] == c) return false;
        }
        else {

            if (!dfs(y, 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() {
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);

    while (m -- ) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        add(x, y, z); add(y, x, z);
    }

    int l = 0, r = 1e9;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;//如果仇恨值小于mid
        else l = mid + 1;
    }

    cout << r << endl;

    return 0;
}

SCC

/*
tarjan算法缩点，找到入度为零的点的个数，然后键边的个数减一
将缩点后的图变成一个强连通分量需要多少条条边
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

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

int n;
int h[N], e[M], ne[M], idx;
int stk[N], top;
int dfn[N], low[N], timestamp;
bool ins[N];
int id[N], scc_cnt, Size[N];//元素所属强连通分量位置，强连通分量下标，强连通分量内节点个数
int din[N], dout[N];//点的入度
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}

void tarjan(int x) {
    dfn[x] = low[x] = ++ timestamp;
    stk[++ top] = x; ins[x] = true;

    for (int i = h[x]; ~i; i = ne[i]) {
        int y = e[i];

        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
        }
        else if (ins[y]) low[x] = min(low[x], dfn[y]);
    }

    if (dfn[x] == low[x]) {
        ++ scc_cnt;
        int y;
        do {
            y = stk[top -- ];
            ins[y] = false;
            id[y] = scc_cnt;
            Size[scc_cnt] ++;
        }while (y != x);
    }
}

int main() {
    scanf("%d", &n);

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

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

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

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

    cout << max(1, a) << endl;
    cout << (scc_cnt == 1 ? 0 : max(a, b)) << endl;

    return 0;
}

tarjan缩点

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

using namespace std;

const int N = 10010, M = 50010;

int n, m;
int h[N], e[M], ne[M], idx;
int dfn[N], low[N], timestamp;
int stk[N], top;
bool ins[N];
int id[N], scc_cnt, Size[N];
int dout[N];

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

void tarjan(int x) {
  dfn[x] = low[x] = ++ timestamp;
  stk[++ top] = x; ins[x] = true;

  for (int i = h[x]; ~i; i = ne[i]) {
    int y = e[i];

    if (!dfn[y]) {
      tarjan(y);
      low[x] = min(low[x], low[y]);
    }
    else if (ins[y]) 
      low[x] = min(low[x], dfn[y]);
  }

  if (dfn[x] == low[x]) {
    ++ scc_cnt;
    int y;
    do {
      y = stk[top -- ];
      ins[y] = false;
      id[y] = scc_cnt;
      Size[scc_cnt] ++;
    }while (y != x);
  }
}

int main() {
  scanf("%d%d", &n, &m);

  memset(h, -1, sizeof h);

  while (m -- ) {
    int a, b; scanf("%d%d", &a, &b);
    add(a, b);
  }

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

  for (int x = 1; x <= n; x ++ ) 
    for (int i = h[x]; ~i; i = ne[i]) {
      int y = e[i];
      int a = id[x], b = id[y];
      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;
}

spfa

/*
s[i] >= s[i - 1]  add(i - 1, i, 0);
s[i] - s[ i - 1] <= 1，s[i - 1] >= s[i] - 1   add(i, i - 1, -1);
s[r] - s[l - 1] >= c  s[r] >= s[l - 1] + c    add(l-1, r, c)
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 50010, M = N * 3;

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

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

void spfa() {
    memset(dist, -0x3f, sizeof dist);
    dist[0] = 0;
    st[0] = true;
    int hh = 0, tt = 1;
    q[0] = 0;

    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = false;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] < dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = true;
                }
            }
        }
    }
}
int main() {
    scanf("%d", &n);

    memset(h, -1, sizeof h);
    for (int i = 1; i <= 50009; i ++ ) {
        add(i - 1, i, 0);
        add(i, i - 1, -1);
    }
    for (int i = 0; i < n; i ++ ) {
        int x, y, z; scanf("%d%d%d", &x, &y, &z);
        x ++, y ++;
        add(x - 1, y, z);
    }

    spfa();

    cout << dist[50001] << endl;

    return 0;
}

SPFA求最短路，判断负环

/*
spfa求最长路径
我们所求的为dist的最小值，
dist[x] >= dist[y] + c1 >= .... >= dist[0] + C
要求的是最小值，那么不等式满足的是放缩，即求最大路径
1 x >= y y >= x . dist[x] >= dist[y] 从y到x的一条路径，c=0. dist[y] >= dist[x] 从x到y的一条路径c=0 add(x, y, 0); add(y, x, 0);
2 y >= x + 1 dist[y] >= dist[x] + 1 从x到y的一条路径，c=1 add(x, y, 1);
3 x >= y dist[x] >= dist[y] 从y走到x的一条路径，c=0  add(y, x, 0);
4 x >= y + 1 dist[x] >= dist[y] + 1 从y走到x的一条路径，c=1 add(y, x, 1);
5 y >= x dist[y] >= dist[x] 从x走到y的一条路径，c=0 add(x, y, 0);
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;

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

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

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

bool spfa() {
    memset(dist, -0x3f, sizeof dist);//求最长路径，要将它先初始化为很小的负数
    dist[0] = 0;//我们所求的最小值，就是从0号点走向个点的各种路径中的最大值。
    int tt = 1;
    q[tt ++ ] = 0;

    while (tt) {
        int x = q[-- tt];

        st[x] = false;        
        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i], z = w[i];

            if (dist[y] < dist[x] + z) {
                dist[y] = dist[x] + z;
                cnt[y] = cnt[x] + 1;

                if (cnt[y] > n) return true;//有n+1个点，包括0号点
                if (!st[y]) {
                    q[tt ++ ] = y;
                    st[y] = true;
                }
            }
        }
    }

    return false;
}

int main() {
    scanf("%d%d", &n, &m);

    memset(h, -1, sizeof h);
    while (m -- ) {
        int t, x, y; scanf("%d%d%d", &t, &x, &y);

        if (t == 1) add(x, y, 0), add(y, x, 0);
        else if (t == 2) add(x, y, 1);
        else if (t == 3) add(y, x, 0);
        else if (t == 4) add(y, x, 1);
        else add(x, y, 0);
    }

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

    if (spfa()) puts("-1");//如果存在正环，就错了
    else {
        LL ans = 0;
        for (int i = 1; i <= n; i ++ ) ans += dist[i];
        cout << ans << endl;
    }

    return 0;
}

0/1分数规划，二分求索答案

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

using namespace std;

const int N = 1010, M = 5050;

int n, m;
int wf[N];
int h[N], e[M], wt[M], ne[M], idx;
int cnt[N];
double dist[N];
bool st[N];
int q[N];

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

bool check(double mid) {
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ ) {
        q[tt ++ ] = i;
        st[i] = true;
    }

    while (hh != tt) {
        int x = q[hh ++ ];
        if (hh == N) hh = 0;
        st[x] = false;

        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i];
            double z = wf[x] - mid * wt[i];

            if (dist[y] < dist[x] + z) {
                dist[y] = dist[x] + z;
                cnt[y] = cnt[x] + 1;

                if (cnt[y] >= n) return true;
                if (!st[y]) {
                    st[y] = true;
                    q[tt ++ ] = y;
                    if (tt == N) tt = 0;
                }
            }
        }
    }

    return false;
}
int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);

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

    for (int i = 0; i < m; i ++ ) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z);
    }

    double l = 0, r = 1e6;
    while (r - l > 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", l);

    return 0;
}

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

using namespace std;

const int N = 1010, M = 5050;

int n, m;
int wf[N];
int h[N], e[M], wt[M], ne[M], idx;
int cnt[N];
double dist[N];
bool st[N];
int q[N];

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

bool check(double mid) {
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    queue<int> q;
    for (int i = 1; i <= n; i ++ ) {
        q.push(i);
        st[i] = true;
    }

    while (q.size()) {
        int x = q.front(); q.pop();
        st[x] = false;

        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i];
            double z = wf[x] - mid * wt[i];

            if (dist[y] < dist[x] + z) {
                dist[y] = dist[x] + z;
                cnt[y] = cnt[x] + 1;

                if (cnt[y] >= n) return true;
                if (!st[y]) {
                    st[y] = true;
                    q.push(y);
                }
            }
        }
    }

    return false;
}
int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);

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

    for (int i = 0; i < m; i ++ ) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z);
    }

    double l = 0, r = 1e6;
    while (r - l > 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", l);

    return 0;
}

0/1分数规划，二分求索答案

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

using namespace std;

const int N = 1010, M = 5050;

int n, m;
int wf[N];
int h[N], e[M], wt[M], ne[M], idx;
int cnt[N];
double dist[N];
bool st[N];
int q[N];

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

bool check(double mid) {
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ ) {
        q[tt ++ ] = i;
        st[i] = true;
    }

    while (hh != tt) {
        int x = q[hh ++ ];
        if (hh == N) hh = 0;
        st[x] = false;

        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i];
            double z = wf[x] - mid * wt[i];

            if (dist[y] < dist[x] + z) {
                dist[y] = dist[x] + z;
                cnt[y] = cnt[x] + 1;

                if (cnt[y] >= n) return true;
                if (!st[y]) {
                    st[y] = true;
                    q[tt ++ ] = y;
                    if (tt == N) tt = 0;
                }
            }
        }
    }

    return false;
}
int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);

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

    for (int i = 0; i < m; i ++ ) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z);
    }

    double l = 0, r = 1e6;
    while (r - l > 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", l);

    return 0;
}

0/1分数规划，二分求索答案

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

using namespace std;

const int N = 1010, M = 5050;

int n, m;
int wf[N];
int h[N], e[M], wt[M], ne[M], idx;
int cnt[N];
double dist[N];
bool st[N];
int q[N];

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

bool check(double mid) {
    memset(dist, 0, sizeof dist);
    memset(cnt, 0, sizeof cnt);
    memset(st, 0, sizeof st);

    int hh = 0, tt = 0;
    for (int i = 1; i <= n; i ++ ) {
        q[tt ++ ] = i;
        st[i] = true;
    }

    while (hh != tt) {
        int x = q[hh ++ ];
        if (hh == N) hh = 0;
        st[x] = false;

        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i];
            double z = wf[x] - mid * wt[i];

            if (dist[y] < dist[x] + z) {
                dist[y] = dist[x] + z;
                cnt[y] = cnt[x] + 1;

                if (cnt[y] >= n) return true;
                if (!st[y]) {
                    st[y] = true;
                    q[tt ++ ] = y;
                    if (tt == N) tt = 0;
                }
            }
        }
    }

    return false;
}
int main() {
    cin >> n >> m;

    memset(h, -1, sizeof h);

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

    for (int i = 0; i < m; i ++ ) {
        int x, y, z; cin >> x >> y >> z;
        add(x, y, z);
    }

    double l = 0, r = 1e6;
    while (r - l > 1e-4) {
        double mid = (l + r) / 2;
        if (check(mid)) l = mid;
        else r = mid;
    }

    printf("%.2lf\n", l);

    return 0;
}

SPFA判断负环

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

using namespace std;

const int N = 510, M = 5210;

int n, m1, m2;
int h[N], e[M], w[M], ne[M], idx;
int dist[N], cnt[N];
bool st[N];
queue<int> q;

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

bool spfa(){
    memset(dist, 0, sizeof dist);
    memset(st, 0, sizeof st);
    memset(cnt, 0, sizeof cnt);

    for (int i = 1; i <= n; i ++ ) q.push(i), st[i] = true;

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

        st[x] = false;
        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i], z = w[i];
            if (dist[y] > dist[x] + z) {
                dist[y] = dist[x] + z;
                cnt[y] = cnt[x] + 1;

                if (cnt[y] >= n) return true;

                if (!st[y]) {
                    st[y] = true;
                    q.push(y);
                }
            }
        }
    }
    return false;
}

int main() {
    int T; scanf("%d", &T);
    while (T -- ) {
        scanf("%d%d%d", &n, &m1, &m2);

        memset(h, -1, sizeof h);
        idx = 0;

        while (m1 -- ) {
            int x, y, z; scanf("%d%d%d", &x, &y, &z);

            add(x, y, z); add(y, x, z);
        }

        while (m2 -- ) {
            int x, y, z; scanf("%d%d%d", &x, &y, &z);
            add(x, y, -z);
        }

        if (spfa()) puts("YES");
        else puts("NO");
    }

    return 0;
}