图论模板

RDC图论模板

连通性

2SAT

struct TwoSat {
    int n;
    vector<int> g[N<<1];
    bool mark[N<<1];
    int S[N<<1], c;
    bool dfs(int x) {
        if (mark[x^1]) return 0;
        if (mark[x]) return 1;
        mark[x] = true;
        S[c++] = x;
        for (int i = 0; i < g[x].size(); i ++)
            if (!dfs(g[x][i]))
                return false;
        return true;
    }
    void init(int n) {
        this->n = n;
        for (int i = 0; i < 2*n; i++) g[i].clear();
        memset(mark, 0, sizeof(mark));
    }
    // x = xval OR y = yval
    void add_clause(int x, int xval, int y, int yval) {
        x = x * 2 + xval;
        y = y * 2 + yval;
        g[x^1].push_back(y);
        g[y^1].push_back(x);
    }
    bool solve() {
        for (int i = 0; i < 2*n; i += 2) {
            if (!mark[i] && !mark[i+1]) {
                c = 0;
                if (!dfs(i)) {
                    while (c > 0) mark[S[--c]] = false;
                    if (!dfs(i+1)) 
                        return false;
                }
            }
        }
        return true;
    }
} Saber;

SCC

#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int N = 20000+10;
int n, m, T;
vector<int> g[N];
struct SCC {
    int pre[N], low[N], sccno[N], dfs_clock, scc_cnt;
    int in[N], out[N], sz[N];
    stack<int> S;
    void dfs(int u) {
        pre[u] = low[u] = ++dfs_clock;
        S.push(u);
        for (int i = 0; i < g[u].size(); i ++) {
            int v = g[u][i];
            if (! pre[v]) {
                dfs(v);
                low[u] = min(low[u], low[v]);
            } else if (!sccno[v]) {
                low[u] = min(low[u], pre[v]);
            }
        }
        if (low[u] == pre[u]) {
            scc_cnt ++;
            for (;;) {
                int x = S.top(); S.pop();
                sccno[x] = scc_cnt;                                                                        
                if (x == u) break;
            }
        }
    }
    void Excalibur(int n) {
        memset(pre, 0, sizeof pre);
        memset(low, 0, sizeof low);
        memset(sccno, 0, sizeof sccno);
        memset(in, 0, sizeof(in));
        memset(out, 0, sizeof(out));
        dfs_clock = scc_cnt = 0;

        for (int i = 1 ;i <= n; i ++)
            if (pre[i] == 0) dfs(i);
        
        for (int i = 1; i <= n; i ++) {
              sz[sccno[i]] ++;
            for (int j = 0; j < g[i].size(); j ++) {
                if (sccno[i] != sccno[g[i][j]])
                    out[sccno[i]] ++, in[sccno[g[i][j]]] ++;
            }
        }
    }
} Saber;

网络流

二分图匹配

int n, m, match[NICO];
bool us[NICO];
vector<int> g[NICO];
bool dfs(int x)
{
    for(int i=0;i<g[x].size();i++)
    {
        if(us[g[x][i]]) continue;
        us[g[x][i]] = 1;
        if(match[g[x][i]] == -1 || dfs(match[g[x][i]]))
        {
            match[g[x][i]] = x; 
            return 1;
        }
    }
    return 0;
}
int hungary()
{
    memset(match, -1, sizeof(match));
    int tot = 0;
    for(int i=0;i<n;i++)
    {
        memset(us, 0, sizeof(us));
        if(dfs(i)) tot ++;
    }
    return tot;
}

DINIC

const int Maxn = 500 + 10;  
const int INF = 0x6fffffff >> 2;  
  
struct edge{  
    int from , to , cap , flow;  
};  
  
struct Dinic{  
    int n,m,s,t;  
    vector<edge> edges;  
    vector<int> f[Maxn];  
    bool vis[Maxn];  
    int d[Maxn];  
    int cur[Maxn];   
    void init(int n) {
        this->n = n;
        edges.clear();
        for (int i = 0; i < Maxn; i ++) f[i].clear();
        memset(d, 0, sizeof(d));
        memset(cur, 0, sizeof(cur));
    }
    void AddEdge(int from,int to,int cap)  
    {  
        edges.push_back((edge){from,to,cap,0});  
        edges.push_back((edge){to,from,0,0});  
        m = edges.size();  
        f[from].push_back(m-2);  
        f[to].push_back(m-1);  
    }  
    bool BFS()   
    {  
        memset(vis,0,sizeof(vis));  
        queue<int> q;  
        q.push(s);  
        d[s] = 0;  
        vis[s] = 1;  
        while(!q.empty())  
        {  
            int x = q.front(); q.pop();  
            for(int i=0;i<f[x].size();i++)  
            {  
                edge &e = edges[f[x][i]];  
                //cout<<"to="<<e.to<<"from="<<e.from<<' '<<e.flow<<' '<<e.cap<<' '<<vis[e.to]<<endl;  
                if(!vis[e.to] && e.flow < e.cap) //只考虑残留网络中的弧   
                {  
                    vis[e.to] = 1;  
                    d[e.to] = d[x] + 1;//层次图  
                    q.push(e.to);   
                }  
            }  
        }  
        return vis[t];//能否到汇点，不能就结束   
    }  
    int DFS(int x,int a)//x为当前节点，a为当前最小残量   
    {  
        if(x == t || a == 0) return a;  
        int flow = 0 , r;  
          
        for(int& i = cur[x];i < f[x].size();i++)  
        {  
            edge& e = edges[f[x][i]];  
            if(d[x] + 1 == d[e.to] && (r = DFS(e.to , min(a,e.cap - e.flow) ) ) > 0 )  
            {  
                e.flow += r;  
                edges[f[x][i] ^ 1].flow -= r;  
                flow += r;//累加流量   
                a -= r;  
                if(a == 0) break;  
            }  
        }  
        return flow;  
    }  
    int MaxFlow(int s,int t)  
    {  
        this->s = s; this->t = t;  
        int flow = 0;  
        while(BFS())  
        {      
            memset(cur,0,sizeof(cur));  
            flow += DFS(s,INF);  
            //printf("%d\n", flow);
        }  
        return flow;  
    }  
} G;  

最短路生成树什么的

Dijkstra

模板里有这种东西大概是一件很卜的事

typedef pair<int, int> pii;
vector<pii> G[N];
int dis[N], vis[N];
void dijkstra(int src) {
    for (int i = 0; i < N; i ++)
        dis[i] = INF, vis[i] = 0;
    dis[src] = 0;
    priority_queue< pii, vector<pii>, greater<pii> > que; que.push(make_pair(0,src));
    while (que.size()) {
        int fi = que.top().first;
        int se = que.top().second;
        que.pop();
        if (vis[se]) continue;
        vis[se] = 1;
        for (int i = 0; i < G[se].size(); i ++) {
            int nex = G[se][i].second;
            if (dis[nex] > dis[se] + G[se][i].first) {
                dis[nex] = dis[se] + G[se][i].first;
                que.push(make_pair(dis[nex], nex));
            }
        }
    }
}

次小生成树

maxcost 数组的维护O(N^2), 施展倍增可以O(NlogN)

int vis[N], pre[N];
int dis[N][N], d[N], maxcost[N][N];

int prim(int s) {
    int res = 0;
    memset(maxcost, 0, sizeof(maxcost));
    for (int i = 1; i <= n; i ++)
        vis[i] = 0, d[i] = INF, pre[i] = i;
    d[s] = 0;
    for (int i = 1; i <= n; i ++) {
        int mx = INF; int index = -1;
        for (int j = 1; j <= n; j ++) {
            if (!vis[j] && d[j] < mx) {
                mx = d[j];
                index = j;
            }
        }
        if (index == -1) break;
        for (int j = 1; j <= n; j ++)
            if (vis[j])
                maxcost[index][j] = maxcost[j][index] = 
                max(maxcost[pre[index]][j], mx);
        res += mx;
        vis[index] = 1;
        for (int j = 1; j <= n; j ++) {
            if (!vis[j] && dis[index][j] < d[j]) {
                d[j] = dis[index][j];
                pre[j] = index;
            }
        }
    }
    return res;
} 

LCA倍增

int fa[N][20], dep[N], sum[N][20];
void dfs(int u, int p) {
    vis[u] = 1;
    for (int i = 0; i < g[u].size(); i ++) {
        int v = g[u][i].first;
        if (v == p) continue;
        dep[v] = dep[u] + 1;
        fa[v][0] = u;
        sum[v][0] = g[u][i].second;
        dfs(v, u);    
    }
}
void init_LCA() {
    for (int i = 1; i <= cnt; i ++) if (! vis[i]) {
        dep[i] = 1, fa[i][0] = 1; sum[i][0] = 0;
        dfs(i, -1);
    }
    for (int i = 1; i < 20; i ++) {
        for (int j = 1; j <= cnt; j ++) {
            sum[j][i] = sum[j][i-1] + sum[fa[j][i-1]][i-1];
            fa[j][i] = fa[fa[j][i-1]][i-1];
        }
    }
}
int query(int u, int v) {
    int ret = 0;

    if (dep[u] < dep[v]) swap(u, v);
    int dt = dep[u] - dep[v];
    for (int i = 0; i < 20; i ++) {
        if ( (dt >> i) & 1 )
            ret += sum[u][i], u = fa[u][i];
    }
    
    if (u == v) return ret; // return u
    for (int i = 19; i >= 0; i --) {
        if (fa[u][i] != fa[v][i])
            ret += sum[u][i] + sum[v][i], u = fa[u][i], v = fa[v][i];
    }
    ret += sum[u][0] + sum[v][0];
    // return fa[u][0]
    return ret;
}

最小树形图

树形图设计者？

排骨龙说的王大拿，心情好的时候有关弄清一下。

if 卜 : return -1

const int MAXV = 1000;
const int MAXE = 40000;
const int INF = 0x3f3f3f3f;

//求具有V个点,以root为根节点的图map的最小树形图

int Excalibur(int root, int V, int map[MAXV + 7][MAXV + 7]){
    bool visited[MAXV + 7];
    bool flag[MAXV + 7];//缩点标记为true,否则仍然存在
    int pre[MAXV + 7];//点i的父节点为pre[i]
    int sum = 0;//最小树形图的权值
    int i, j, k;
    for(i = 0; i <= V; i++) flag[i] = false, map[i][i] = INF;
    pre[root] = root;
    while(true){
        for(i = 1; i <= V; i++){//求最短弧集合E0
            if(flag[i] || i == root) continue;
            pre[i] = i;
            for(j = 1; j <= V; j++)
                if(!flag[j] && map[j][i] < map[pre[i]][i])
                    pre[i] = j;
            if(pre[i] == i) return -1;
        }
        for(i = 1; i <= V; i++){//检查E0
            if(flag[i] || i == root) continue;
            for(j = 1; j <= V; j++) visited[j] = false;
            visited[root] = true;
            j = i;//从当前点开始找环
            do{
                visited[j] = true;
                j = pre[j];
            }while(!visited[j]);
            if(j == root)continue;//没找到环
            i = j;//收缩G中的有向环
            do{//将整个环的取值保存,累计计入原图的最小树形图
                sum += map[pre[j]][j];
                j = pre[j];
            }while(j != i);
            j = i;
            do{//对于环上的点有关的边,修改其权值
                for(k = 1; k <= V; k++)
                    if(!flag[k] && map[k][j] < INF && k != pre[j])
                        map[k][j] -= map[pre[j]][j];
                j = pre[j];
            }while(j != i);
            for(j = 1; j <= V; j++){//缩点,将整个环缩成i号点,所有与环上的点有关的边转移到点i
                if(j == i) continue;
                for(k = pre[i]; k != i; k = pre[k]){
                    if(map[k][j] < map[i][j]) map[i][j] = map[k][j];
                    if(map[j][k] < map[j][i]) map[j][i] = map[j][k];
                }
            }
            for(j = pre[i]; j != i; j = pre[j]) flag[j] = true;//标记环上其他点为被缩掉
            break;//当前环缩点结束,形成新的图G',跳出继续求G'的最小树形图
        }
        if(i > V){//如果所有的点都被检查且没有环存在,现在的最短弧集合E0就是最小树形图.累计计入sum,算法结束
            for(i = 1; i <= V; i++)
                if(!flag[i] && i != root) sum += map[pre[i]][i];
            break;
        }
    }
    return sum;
}

一些卜

最大团

对生命安全概不负责

反正用不上！

/* 
Gragh: 0-index
dp[i]: count of node [i, n-1]
*/

#include <iostream>
using namespace std;
const int NICO = 102;
int n, mat[NICO][NICO];
int dp[NICO]; // [i, n-1] 最大团节点数
int mx;       // 记录最大团节点个数
int stack[NICO][NICO];

void dfs(int N, int num, int step) {
    if(num == 0) {
        if(step > mx) mx = step;
        return;
    }
    for(int i = 0; i < num; i ++) {
        int k = stack[step][i];
        if(step + N - k <= mx) return;
        if(step + dp[k] <= mx) return;

        int cnt = 0;
        for(int j = i + 1; j < num; j ++) {
            if(mat[k][stack[step][j]]) {
                stack[step+1][cnt ++] = stack[step][j];
            }
        }
        dfs(N, cnt, step + 1);
    }
}

void run(int N) {
    mx = 0;
    for(int i = N - 1; i >= 0; i --) {
        int sz = 0;
        for(int j = i + 1; j < N; j ++) {
            if(mat[i][j]) stack[1][sz ++] = j;
        }
        dfs(N, sz, 1);
        dp[i] = mx;
    }
}

int main() {
    scanf("%d", &n);
    for(int i = 0; i < n; i ++) {
        for(int j = 0; j < n; j ++) {
            scanf("%d", &mat[i][j]);
        }
    }
    run(n);
    printf("%d\n", mx);
}