[原创]图论 [未完成 待续~待修改]

[原创]图论 [未完成 待续~待修改]

2017-01-26 21:45:01 Tabris_ 阅读数：473

---

博客爬取于2020-06-14 22:39:11
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/54746580

---

#图

图的表示方法

矩阵

二维数组 map[i][j] 表示i到j的边 值为边得大小 ,定义一个值代表不存在这条边 一般为0
空间复杂度$O(n^{2})$

vector

vectorG[N];
G[i][j] 表示有一条i->j的有向边

void add(int u,int v){
    G[u].push_back(v);
}

空间复杂度$O(e)$

前向星

struct edge{
    int to,next,w;
}G[N<<1];
int head[N],tot;
void add(int u,int v,int w){
    G[tot].w=w,G[tot].to=v,G[tot].next=head[u],head[u]=tot++;
}

空间复杂度$O(e)$

最短路

floyd

不解释

dijkstra

vector<pair<int ,int > >G[N];
int d[N];

int main(){

    while(~scanf("%d%d",&m,&n)){
        for(int i=1;i<=n;i++)d[i]=2e9+7,G[i].clear();
        d[n]=0;
        for(int i=1,u,v,w;i<=m;i++){
            scanf("%d%d%d",&u,&v,&w);
            G[u].push_back(make_pair(v,w));
            G[v].push_back(make_pair(u,w));
        }

        priority_queue<pair<int ,int> >q;
        q.push(make_pair(-d[n],n));
        while(!q.empty()){
            int u =q.top().second;q.pop();
            for(int i=0,v;i<G[u].size();i++){
                v=G[u][i].first;
                if(d[v]>d[u]+G[u][i].second){
                    d[v]=d[u]+G[u][i].second;
                    q.push(make_pair(-d[v],v));
                }
            }

        }
        if(d[n]==2e9+7) puts("-1");
        else            printf("%d\n",d[1]);

    }
    return 0;
}

SPFA

LL d[N];
int inq[N],n,m,q;
LL spfa(int s,int t){
    for(int i=1;i<=n;i++) d[i]=2e14+7,inq[i]=0;

    queue<int >q;
    q.push(s);d[s]=0,inq[s]=1;
    while(!q.empty()){
        int u =q.front();q.pop();
        inq[u]=0;
        for(int i=head[u],v;i!=-1;i=G[i].next){
            v=G[i].to;
            if(d[v]>d[u]+G[i].w){
                d[v]=d[u]+G[i].w;
                if(inq[v]==1) continue;
                inq[v]=1;
                q.push(v);
            }
        }
    }

    return d[t];
}

强连通

vector<int>G[N];
vector<pair<int,int> >G2[N];

int low[N],dfn[N],w[N],d[N];
int vis[N],val[N];
int color[N],cnt,tot;
int mystack[N],len;

void dfs(int u){vis[u]=1;
    dfn[u]=low[u]=++cnt;
    mystack[++len]=u;
    int gz=G[u].size();
    for(int to,i=0;i<gz;i++){
        to=G[u][i];
        if(vis[to]==0) dfs(to);
        if(vis[to]==1) low[u]=min(low[u],low[to]);
    }

    if(dfn[u]==low[u]){
        ++tot;
        do{
            val[tot]+=w[mystack[len]];
            color[mystack[len]]=tot;
            vis[mystack[len]]=2;
        }while(mystack[len--]!=u);
    }
}

int n,m;
int main(){
    scanf("%d%d",&n,&m);
    cnt=tot=len=0;
    for(int i=1;i<=n;i++)    scanf("%d",&w[i]);

    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        G[u].push_back(v); //看是有向图还是无向图
    }

    //缩点
    for(int i=1;i<=n;i++)   if(vis[i]==0)dfs(i);

    //建新图

    for(int i=1,gz;i<=n;i++){vis[i]=0,d[i]=0;
        gz=G[i].size();
        for(int j=0,to;j<gz;j++){
            to=G[i][j];
            if(color[i]!=color[to])
                G2[color[i]].push_back(make_pair(val[color[to]],color[to]));
        }
    }
    return 0;
}

二分图匹配

算法介绍
最大匹配数：最大匹配的匹配边的数目
最小点覆盖数：选取最少的点，使任意一条边至少有一个端点被选择
最大独立数：选取最多的点，使任意所选两点均不相连
最小路径覆盖数：对于一个 DAG（有向无环图），选取最少条路径，使得每个顶点属于且仅属于一条路径。路径长可以为 0（即单个点）。

定理1：最小点覆盖数 = 最大匹配数（这是 Konig 定理）
定理2：最大独立数 = 顶点数 - 最大匹配数
定理3：最小路径覆盖数 = 顶点数 - 最大匹配数

匈牙利算法求解二分图匹配问题

int k,n,m;
int match[N];
int vis[N];
vector<int >G[N];

int tot,a;
int col[N];
//二分图染色  用来判断是不是二分图
bool color(int s){
    queue<int>q;
    q.push(s);col[s]=1;
    while(!q.empty()){
        int u = q.front();q.pop();
        tot++;
        if(col[u]==1) a++;
        int gz=G[u].size();
        for(int i=0,to;i<gz;i++){
            to=G[u][i];
            if(col[to]==0){
                col[to]=3-col[u];
                q.push(to);
            }
            else if(col[to]==col[u])
                return false;
        }
    }
    return true;
}

bool findi(int u){
    for(int i=0;i<G[u].size();i++){
        int v=G[u][i];
        if(vis[v]==0){
            vis[v]=1;
            if(match[v]==-1||findi(match[v])){
                match[v]=u;
                return true;
            }
        }
    }
    return false;
}

void init(){
    memset(match,-1,sizeof(match));
    for(int i=1;i<=n;i++) G[i].clear(),col[i]=vis[i]=0;
}

void add(int u,int v){
    G[u].push_back(v);
    G[v].push_back(u); //无向图才需要
}

int maxMATCH(){
    int ans = 0;  //ans 是最大匹配数,
    for(int i=1;i<=n;i++){
        memset(vis,0,sizeof(vis));
        if(findi(i)) ans++;
    }
    ans/=2;   //对于无向图的话 需要ans/=2;
    return ans ;
}

bool perfectMATCH(){
    if(maxMATCH()==n) return true;
    else              return false;
}

int main(){
    int _;
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&m);
        init();a=0;
        for(int i=1,u,v;i<=m;i++){
            scanf("%d%d",&u,&v);
            add(u,v);
        }
        /****
        根据题意进行balabala
        */
    }
    return 0;
}

2-SAT

强连通分支及其应用（2-SAT）总结

2-SAT

强联通分量一个很重要的用途就是解布尔方程可满足性问题（SAT）。需要学习这一部分知识我们需要一点布尔代数的知识。

下文中我们约定（^表示交v表示并）

例如：（a v b v …）^（c v d v …）^…

这样的我们叫做合取范式。其中（a v b v …）这样的叫做子句。类似a，b…叫做文字。

我们把合取范式中一个子句中包含文字不超过两个的问题成为2-SAT问题。在SAT问题中只有这一类我们可以用线性时间内得出答案。

最常规的2-SAT题目分为大致两种，一种是让你判断有没有解，另一种是让你输出一组解。针对这两种给出模版。

在这之前先来介绍一下2-SAT题目的大致解题步骤：

对于2-SAT问题我们需要构建一张有向图每个文字拆为两个节点 例如 a 变为 a， !a

首先我们从题目中总结出来的都是一些比较杂乱的逻辑表达式，不过一般都是两两之间的关系，我们需要做的第一步是化简成用^连接。然后对于每个子句建边。

建边的规则是这样的 a -> b那么在有向图中建一条a到b的边

我们可能得到的子句有：

a v b 我们可以化简 !a->b ^ !b->a

a -> b 直接连边

a 转化为!a -> a

其中每个文字及其的非对应相应的结点，若是出现在文字前有非的关系例如 !a v b 那么变通一下 就化成 a -> b ^ !b -> !a就可以了。

到这里我们要做的事（建图）就完成了，接下来交给模版，我们来看一下模版做了什么：

首先我们对建完的有向图求强连通分支，若是出现有一个逻辑变量和他的反在同一个联通分之内就无解，否则有解。

若a所在的强连通分支的拓扑序在!a之后a为真，否则为反。怎么样很简单吧。

vector<int> G[N];
vector<int> G2[N];

vector<int> S;
int vis[N] ;  //标记数组
int sccno[N]; //记录数组 sccno[i] 记录  i属于哪个联通分支
int scc_cnt;

int n;

void dfs1(int u){
    if(vis[u]) return ;
    vis[u] = true;
    for(int i = 0; i < G[u].size(); i++){
        dfs1(G[u][i]);
    }
    S.push_back(u);
}

void dfs2(int u){
    if(sccno[u]) return;
    sccno[u] = scc_cnt;
    for(int i = 0; i < G2[u].size(); i++){
        dfs2(G2[u][i]);
    }
}

void find_scc(int n){
    scc_cnt = 0;
    S.clear();
    memset(vis , 0 , sizeof(vis));
    memset(sccno , 0 , sizeof(sccno));
    for(int i = 0; i < n; i++) dfs1(i);
    for(int i = n - 1; i >= 0; i--) if(!sccno[S[i]]){
        scc_cnt++;
        dfs2(S[i]);
    }
}

void AddEdge(int u , int v) {
    G[u].push_back(v);
    G2[v].push_back(u);
}

int main(){
    /***
    输入数据
    */

    /***
    加边  边未两者不能匹配的
    example ：
    {u,v}  当选择u的时候一定不能选择v ,需要选择v';
    */

    find_scc(2 * n);  //注意x2

    for(int i = 0; i < n; i++){
        if(sccno[i] == sccno[i + n]){
            //如果有x与x'同时被取或者未取，则匹配失败
            puts("NO");
            return 0;
        }
    }

    puts("YES");
    for(int i = 0; i < n; i++){
        if(sccno[i] > sccno[i + n]){
            //相关 i;
        }
        else {
            //相关 i';
        }
    }
    return 0;
}
/********************************************************/
/****************************************
     2-SAT kosaraju算法
     By 小豪
*****************************************/
const int LEN = 200000+10;
vector<int> Map[LEN], rMap[LEN], vs;
int n, m, vis[LEN], sccn[LEN];

void dfs(int v){
    vis[v] = 1;
    for(int i=0; i<Map[v].size(); i++)
        if(!vis[Map[v][i]]) dfs(Map[v][i]);
    vs.PB(v);
}

void rdfs(int v, int f){
    vis[v] = 1;
    sccn[v] = f;
    for(int i=0; i<rMap[v].size(); i++)
        if(!vis[rMap[v][i]]) rdfs(rMap[v][i], f);
}

int scc(){
     memset(vis, 0, sizeof vis);
     vs.clear();
     for(int i=0; i<2*n; i++) if(!vis[i]) dfs(i);
     memset(vis, 0, sizeof vis);
     int k = 0;
     for(int i = vs.size()-1; i>=0; i--) if(!vis[vs[i]]) rdfs(vs[i], k++);
     return k;
}

void addedge(int a, int b){
    Map[a].PB(b);
    rMap[b].PB(a);
}

void solve()
{
    scc();
    for(int i=0; i<2*n; i+=2)
        if(sccn[i] == sccn[i+1]){
                //printf("No solution.\n");
        　　　　 //无解
            return ;
        }
    for(int i=0; i<n; i++){
        if(sccn[i*2] > sccn[i*2+1]) printf("Yes\n");
        else printf("No\n");
    }
}

网络流

网络流各种骚操作

dinic(没有当前弧优化

const int MAXN = 210;
const int MAXM = 210*210;
const int INF = 0x3f3f3f3f;

struct Edge {
    int v, f;
    int next;
} edge[MAXM];

int n, m;
int cnt;

int head[MAXN], level[MAXN];
int q[MAXN];

void read_graph(int u, int v, int f) {
    edge[cnt].v = v, edge[cnt].f = f;
    edge[cnt].next = head[u], head[u] = cnt++;
    edge[cnt].v = u, edge[cnt].f = 0;  //增加一条反向弧，容量为0
    edge[cnt].next = head[v], head[v] = cnt++;
}
//BFS构建层次网络：
int bfs(int s, int t) { //构建层次网络
    memset(level, 0, sizeof(level));
    level[s] = 1;
    int front = 0, rear = 1;
    q[front] = s;
    while(front < rear) {
        int x = q[front++];
        if(x == t) return 1;
        for(int e = head[x]; e != -1; e = edge[e].next) {
            int v = edge[e].v, f = edge[e].f;
            if(!level[v] && f) {
                level[v] = level[x] + 1;
                q[rear++] = v;
            }
        }
    }
    return 0;
}
//DFS找寻增广路：
int dfs(int u, int maxf, int t) {
    if(u == t) return maxf;
    int ret = 0;
    for(int e = head[u]; e != -1; e = edge[e].next) {
        int v = edge[e].v, f = edge[e].f;
        if(level[u] + 1 == level[v] && f) {
            int Min = min(maxf-ret, f);
            f = dfs(v, Min, t);
            edge[e].f -= f;
            edge[e^1].f += f;
            ret += f;
            if(ret == maxf) return ret;
        }
    }
    return ret;
}

int Dinic(int s, int t) { //Dinic
    int ans = 0;
    while(bfs(s, t)) ans += dfs(s, INF, t);
    return ans;
}

int main() {
    while(~scanf("%d%d",&m,&n)){
        cnt = 0;
        memset(head, -1, sizeof(head));
        for(int x,y,v;m--;){
            scanf("%d%d%d",&x,&y,&v);
            read_graph(x,y,v);
        }
        printf("%d\n",Dinic(1,n));
    }
    return 0;
}

树

树被定义为没有圈的连通图，具有以下几个性质：

1. 在树中去掉一条边后所得的图是不连通的。
2. 在树中添加一条边后所得的图一定存在圈。
3. 树的每一对顶点 U 和 V 之间有且仅有一条路径。

树的直径

树的直径(Diameter)是指树上的最长简单路。

直径的求法：两遍搜索 (BFS or DFS)
任选一点w为起点，对树进行搜索，找出离w最远的点u。
以u为起点，再进行搜索，找出离u最远的点v。则u到v的路径长度即为树的直径。

树的重心

树的重心：找到一个点，其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡。
树的重心可以通过简单的两次搜索求出，第一遍搜索求出每个结点的子结点数量son[u]，第二遍搜索找出使max{son[u],n-son[u]-1}最小的结点。
实际上这两步操作可以在一次遍历中解决。对结点u的每一个儿子v，递归的处理v，求出son[v]，然后判断是否是结点数最多的子树，处理完所有子结点后，判断u是否为重心。

例题 1655

int n;

vector<int >G[N];
void add(int u,int v){G[u].push_back(v);}

int sz[N],siz,zx;

void dfs(int u,int f=0){
    sz[u]=1;int mx=0;
    int gz=G[u].size();
    for(int i=0,to;i<gz;i++){
        to = G[u][i];
        if(to == f) continue;
        dfs(to,u);
        sz[u]+=sz[to];
        mx=max(mx,sz[to]);
    }
    mx=max(mx,n-sz[u]);
    if(mx==siz&&u<zx) zx=u;
    if(mx<siz) zx=u,siz=mx;
}

int main(){
    int _;
    for(scanf("%d",&_);_--;){
        scanf("%d",&n);
        for(int i=1,u,v;i<n;i++){
            scanf("%d%d",&u,&v);
            add(u,v);add(v,u);
        }
        siz = n*10; dfs(1);
        printf("%d %d\n",zx,siz);
        for(int i=1;i<=n;i++) G[i].clear();
    }
    return 0;
}