Graph

Posted on | Edited on | In | Views:

Graph

存图

前向星

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
struct Edge{
    int u,v,nxt;
    ll w;
}edge[2*M];
int fir[N],cnt,FLAG;
void addedge(int u,int v,ll w){
    if(!FLAG){
        mem_1(fir);
        FLAG=1;
        cnt=0;
    }
    //edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
struct node{
    int u;
    ll d;
    node(int u,ll d):u(u),d(d){}
    bool operator < (const node &a) const{
        return d>a.d;
    }
};

最短路

floyd-warshall

1
2
3
4
5
6
//Floyd-Warshall算法核心语句   
for(k=1;k<=n;k++)//先枚举中转点   
    for(i=1;i<=n;i++)//枚举起点
        for(j=1;j<=n;j++)//枚举终点   
            if(e[i][k]<inf && e[k][j]<inf && e[i][j]>e[i][k]+e[k][j])   
                e[i][j]=e[i][k]+e[k][j];

bellman

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
bool bellman_ford(int start, int n){
    for (int i = 1; i <= n; i++)dist[i] = INF;
    dist[start] = 0;
    for (int i = 1; i<n; i++){
        bool flag = false;
        for (int j = 0; j<E.size(); j++){
            int u = E[j].u;
            int v = E[j].v;
            int cost = E[j].cost;
            if (dist[v]>dist[u] + cost){
                dist[v] = dist[u] + cost;
                flag = true;
            }
        }
        if (!flag)return true;
    }
    for (int j = 0; j<E.size(); j++)
    if (dist[E[j].v]>dist[E[j].u] + E[j].cost) return false;
    return true;
}

SPFA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
const int inf=0x3f3f3f3f;
int cnt[509],bm[109];
bool used[509];
vector< pair<int,int> > edge[509];
bool spfa(int st){
    for(int i=1; i<=n; i++)bm[i]=inf;
    memset(used,0,sizeof(used));
    memset(cnt,0,sizeof(cnt));//记录从起点到i点的最短距离包含点的个数
    bm[st]=0; cnt[st]=1; used[st]=1;
    queue<int> que;
    que.push(st);
    while(!que.empty()){
        int u=que.front();
        used[u]=0; que.pop();
        for(int i=0; i<edge[u].size(); i++){
            int v=edge[u][i].first;
            int w=edge[u][i].second;
            if(bm[v]>bm[u]+w){
                bm[v]=bm[u]+w;
                cnt[v]=cnt[u]+1;
                if(cnt[v]>n) return 0;//存在负环
                if(!used[v]){
                    que.push(v);
                    used[v]=1;
                }
            }
        }
    }
    return 1;
}

堆优dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
struct Edge{
    int u,v,nxt;
    ll w;
}edge[2*M];
int fir[N],cnt,FLAG;
void addedge(int u,int v,ll w){
    if(!FLAG){
        mem_1(fir);
        FLAG=1;
        cnt=0;
    }
    //edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
struct node{
    int u;
    ll d;
    node(int u,ll d):u(u),d(d){}
    bool operator < (const node &a) const{
        return d>a.d;
    }
};
bool used[N];
ll dis[N];
void dijkstra(){
    priority_queue<node> que;
    memset(dis,inf,sizeof(dis));
    dis[1]=0;
    que.push(node(1,dis[1]));
    memset(used,0,sizeof(used));
    while(!que.empty()){
        int u=que.top().u;
        que.pop()
        if(used[u]) continue;
        used[u]=1;
        for(int i=fir[u]; i!=-1; i=edge[i].nxt){
            int v=edge[i].v;
            int w=edge[i].w;
            if(!used[v]&&dis[v]>dis[u]+w){
                dis[v]=dis[u]+w;
                que.push(node(v,dis[v]));
            }
        }
    }
}

dijkstra

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
for(int i=1; i<=n; i++)
        {
            dis[i]=edge[1][i];
            used[i]=1;
        }

        used[1]=0; dis[1]=0;
        for(int i=1; i<=n; i++)
        {
            //printf("ASD\n");
            int minV=inf;
            int id=1;//important

            for(int j=1; j<=n; j++)
                if(used[j]&&minV>dis[j])
                {
                    minV=dis[j];
                    id=j;
                }

            used[id]=0;
            for(int j=1; j<=n; j++)
            {
                if(edge[id][j]<inf&&used[j]&&dis[j]>dis[id]+edge[id][j]) dis[j]=dis[id]+edge[id][j];
            }
        }

差分约束系统

求解差分约束系统，都可以转化成图论的单源最短路径（或最长路径）问题。
我们观察上面例子中的不等式，都是x[i] - x[j] <= a[k]，可以进行移项，成为x[i] <= x[j] + a[k]，我们令a[k] = w(j, i)，dis[i]=x[i],并使i=v,j=u,那么原始就变为：dis[u]+w(u,v)>=dis[v],于是可以联想到最短路模型中的一部分代码
但是好像不等号方向刚好相反，但其实这并不矛盾，上面的代码要实现的是使dis[u]+w(u,v)>dis[v],而对于不等式，我们进行建边的操作：对于每个不等式 x[i] - x[j] <= a[k]，对结点 j 和 i 建立一条 j -> i的有向边，边权为a[k]，求x[n-1] - x[0] 的最大值就是求 0 到n-1的最短路，两者刚好吻合。所以求解差分约束问题就转化为了最短路问题。

差分约束

求解不等式组，当把不等式整理成 $d[a]+w<=d[b]$ 时，我们求最长路。整理成 $d[a]+w>=d[b]$ 时，我们求最短路。在一个未知数定死的情况下，最短路求得是最大值，最长路求得是最小值。

candies

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
int n,m,cnt;
struct Edge
{
    int u,v,w,nxt;
}edge[150005];
int fir[30004];
void addedge(int u,int v,int w)
{
    //edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    edge[cnt].nxt=fir[u];
    fir[u]=cnt++;
}
struct node
{
    int u;
    int d;
    node(int u,int d):u(u),d(d){}
    bool operator < (const node &a) const
    {
        return d>a.d;
    }
};
bool used[30004];
int dis[30004];
void dijkstra()
{
    priority_queue<node> que;
    while(!que.empty()) que.pop();
    for(int i=1; i<=n; i++)
        dis[i]=inf;
    dis[1]=0;
    que.push(node(1,dis[1]));
    memset(used,0,sizeof(used));
    while(!que.empty())
    {
        int u=que.top().u;
        que.pop();
        if(used[u]) continue;
        used[u]=1;
        for(int i=fir[u]; i!=-1; i=edge[i].nxt)
        {
            int v=edge[i].v;
            int w=edge[i].w;
            if(used[v]) continue;
            if(dis[v]>dis[u]+w)
            {
                dis[v]=dis[u]+w;
                que.push(node(v,dis[v]));
            }
        }
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)==2)
    {
        memset(fir,-1,sizeof(fir));
        cnt=0;
        for(int i=1; i<=m; i++)
        {
            int u,v,w;
            scanf("%d%d%d",&u,&v,&w);
            addedge(u,v,w);
        }
        dijkstra();
        printf("%d\n",dis[n]);
    }
    return 0;
}

最小生成树

最大独立集与最大团

最大团

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int n,m,ans;
int used[N];
int cnt[N];//cnt[i] 结点[i,n]构成的最大团的数量
int group[N];
bool edge[N][N];
bool dfs(int u,int dep){
    for(int i=u+1; i<=n; i++){
        if(cnt[i]+dep<=ans)return 0;
        if(edge[u][i]){
            int j=0;
            for(j=0; j<dep; j++){
                if(!edge[i][used[j]])break;
            }
            if(j==dep){
                used[dep]=i;
                if(dfs(i,dep+1))return 1;
            }
        }
    }
    if(dep>ans){
        for(int i=0; i<dep; i++)group[i]=used[i];
        ans=dep;
        return 1;
    }
    return 0;
}
void maxclique(){
    memset(used,0,sizeof(used));
    for(int i=n; i>=1; i--){//n为点数
        used[0]=i;
        dfs(i,1);
        cnt[i]=ans;
    }
}

最大独立集

补图的最大团