【准备5】基础图论问题

本文主要是介绍【准备5】基础图论问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

P1194 买礼物

Problem Link

solution

\(\quad\)这玩意的本质就是最小生成树。如果 a 对 b 有优惠，那么我们将 a 向 b 连一条边，然后将 0 向所有节点连一条权值为 A 的边，最后跑一遍最小生成树即可。

code

#include<bits/stdc++.h>

using namespace std;
struct node {
    int u, v, w;
} e[250000];
int a, b, k, tot = 1, ans, f[555];

bool cmp(node x, node y) {
    return x.w < y.w;
}

int find(int x) {
    if (f[x] == x) return x;
    return f[x] = find(f[x]);
}

int hb(int x, int y) {
    int xx = find(x);
    int yy = find(y);
    if (xx != yy) f[xx] = yy;
}

void build(int x, int y, int z) {
    k++;
    e[k].u = x;
    e[k].v = y;
    e[k].w = z;
}

void kruskal() {
    int j = 1;
    while (j <= k && tot <= b) {
        if (find(e[j].u) != find(e[j].v)) {
            tot++;
            ans += e[j].w;
            hb(e[j].u, e[j].v);
        }
        j++;
    }
}

int main() {
    scanf("%d%d", &a, &b);
    for (int i = 1; i <= b; i++) {
        for (int j = 1; j <= b; j++) {
            int x;
            scanf("%d", &x);
            if (i < j && x != 0) build(i, j, x);
        }
    }
    for (int i = 1; i <= b; i++) build(0, i, a);
    for (int i = 0; i <= b; i++) f[i] = i;
    sort(e + 1, e + k + 1, cmp);
    kruskal();
    printf("%d\n", ans);
    return 0;
}

P1195 口袋的天空

Problem Link

solution

\(\quad\)利用 \(Kruskal\) 算法的思想去解决就可以了。

code

#include<bits/stdc++.h>

#define N 1005
using namespace std;
int n, m, k, x, y, l, sum, ans;
int fa[N];

struct Edge {
    int u, v, w;

    bool operator<(Edge a) const {
        return w < a.w;
    }
} edge[N * 10];

int find(int x) {
    return fa[x] == x ? fa[x] : fa[x] = find(fa[x]);
}

int main() {
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
    }
    sort(edge + 1, edge + m + 1);
    for (int i = 1; i <= m; i++) {
        int fx = find(edge[i].u), fy = find(edge[i].v);
        if (fx != fy) {
            fa[fx] = fy;
            sum++;
            ans += edge[i].w;
        }
        if (sum == n - k) {
            printf("%d", ans);
            return 0;
        }
    }
    puts("No Answer");
    return 0;
}

P1967 [NOIP2013 提高组] 货车运输

Problem Link

solution

\(\quad\)其实本质就是一个最大瓶颈生成树，所以求一个最大生成树，然后用倍增去求就可以了。当然这个题目也是 \(Kruskal\) 重构树的经典应用。

code

#include<bits/stdc++.h>

#define fo(i, j, k) for(register int i=j;i<=k;i++)
#define fd(i, j, k) for(register int i=j;i>=k;i--)
#define ll long long
#define re register
#define file(x) freopen("x.in","r",stdin);freopen("x.out","w",stdout);
#define ios ios::sync_with_stdio(false)
using namespace std;
const int MAXN = 10005;
const int INF = 99999999;
int cnt = 0, ans = 0, n, m, head[MAXN], deep[MAXN], f[MAXN], fa[MAXN][21], w[MAXN][21];
bool vis[MAXN];
struct edge1 {
    int u, v, w;
} e1[100005];
struct edge2 {
    int v, nxt, w;
} e2[100005];

void add(int u, int v, int w) {
    cnt++;
    e2[cnt].v = v;
    e2[cnt].nxt = head[u];
    e2[cnt].w = w;
    head[u] = cnt;
}

bool cmp(edge1 a, edge1 b) {
    return a.w > b.w;
}

int find(int x) {
    while (x != f[x]) x = f[x] = f[f[x]];
    return x;
}

void dfs(int node) {
    vis[node] = 1;
    for (int i = head[node]; i; i = e2[i].nxt) {
        int ev = e2[i].v;
        if (vis[ev]) continue;
        deep[ev] = deep[node] + 1;
        fa[ev][0] = node;
        w[ev][0] = e2[i].w;
        dfs(ev);
    }
}

void kruskal() {
    ans = 0;
    sort(e1 + 1, e1 + 1 + m, cmp);
    fo(i, 1, m) {
        int eu = find(e1[i].u);
        int ev = find(e1[i].v);
        if (eu == ev) continue;
        f[ev] = eu;
        add(e1[i].u, e1[i].v, e1[i].w);
        add(e1[i].v, e1[i].u, e1[i].w);
        ans++;
        if (ans == n - 1) break;
    }
}

int lca(int x, int y) {
    if (find(x) != find(y)) return -1;
    int ans = INF;
    if (deep[x] > deep[y]) swap(x, y);
    for (int i = 20; i >= 0; i--)
        if (deep[fa[y][i]] >= deep[x]) {
            ans = min(ans, w[y][i]);
            y = fa[y][i];
        }
    if (x == y) return ans;
    fd(i, 20, 0) {
        if (fa[x][i] != fa[y][i]) {
            ans = min(ans, min(w[x][i], w[y][i]));
            x = fa[x][i];
            y = fa[y][i];
        }
    }
    ans = min(ans, min(w[x][0], w[y][0]));
    return ans;
}

int main() {
    ios;
    cin >> n >> m;
    fo(i, 1, n) f[i] = i;
    fo(i, 1, m) cin >> e1[i].u >> e1[i].v >> e1[i].w;
    kruskal();
    fo(i, 1, n) {
        if (!vis[i]) {
            deep[i] = 1;
            dfs(i);
            fa[i][0] = i;
            w[i][0] = INF;
        }
    }
    fo(i, 1, 20)fo(j, 1, n) {
            fa[j][i] = fa[fa[j][i - 1]][i - 1];
            w[j][i] = min(w[j][i - 1], w[fa[j][i - 1]][i - 1]);
        }
    int q;
    cin >> q;
    fo(i, 1, q) {
        int x, y;
        cin >> x >> y;
        cout << lca(x, y) << endl;
    }
    return 0;
} 

P2910 [USACO08OPEN]Clear And Present Danger S

Problem Link

solution

\(\quad\)floyd 最短路裸题

code

#include<bits/stdc++.h>

#define maxn 101
#define maxm 10001
using namespace std;
int ans, f[maxn][maxn], m[maxn][maxn], mm, n, a[maxm];

inline void write(int X) {
    if (X < 0) {
        X = ~(X - 1);
        putchar('-');
    }
    if (X > 9) write(X / 10);
    putchar(X % 10 + '0');
}

inline int read() {
    int X = 0;
    bool flag = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') flag = 0;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        X = (X << 1) + (X << 3) + ch - '0';
        ch = getchar();
    }
    if (flag) return X;
    return ~(X - 1);
}

int main() {
    memset(m, 0X3F, sizeof(m));
    n = read();
    mm = read();
    for (int i = 1; i <= mm; i++) a[i] = read();
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            m[i][j] = read();
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                m[i][j] = min(m[i][j], m[i][k] + m[k][j]);
    int p = 1;
    for (int i = 1; i <= mm; i++) {
        ans += m[p][a[i]];
        p = a[i];
    }
    cout << ans;
    return 0;
}

P3366 【模板】最小生成树

Problem Link

solution

\(\quad\)略

code

#include<bits/stdc++.h>

using namespace std;
const int maxn = 1000100l;
int n, m, fa[maxn], tot, cnt, ans;
struct edge {
    int v, w, nxt, u;
} e[maxn];

void add(int u, int v, int w) {
    tot++;
    e[tot].u = u;
    e[tot].v = v;
    e[tot].w = w;
}

bool cmp(edge a, edge b) {
    return a.w < b.w;
}

int find(int x) {
    return (x == fa[x]) ? x : find(fa[x]);
}

void kruskal() {
    sort(e + 1, e + 1 + m, cmp);
    for (int i = 1; i <= m; i++) {
        int eu = find(e[i].u);
        int ev = find(e[i].v);
        if ((eu) == (ev)) continue;
        fa[eu] = ev;
        ans += e[i].w;
        if (++cnt == n - 1) break;
    }
}

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) fa[i] = i;
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    kruskal();
    cout << ans;
    return 0;
}

B3611 【模板】传递闭包

Problem Link

solution

\(\quad\)用 floyd 淦就可以了

code

const int N=110;
int T,n,a[N][N],b[N][N];

inline void solve(){
    n=read();
    FOR(i,1,n)
    FOR(j,1,n) a[i][j]=b[i][j]=read();

    FOR(k,1,n)
    FOR(i,1,n)
    FOR(j,1,n){
        b[i][j]|=b[i][k]&b[k][j];
    }
    FOR(i,1,n){
        FOR(j,1,n) printf("%d ",b[i][j]);
        puts("");
    }
}

P5960 【模板】差分约束算法

Problem Link

solution

\(\quad\)差分约束系统板题

code

#include<bits/stdc++.h>
using namespace std;
const int maxn=100010;
int n,m;
int cnt,head[maxn],tot[maxn];
struct edge
{
	int v,nxt,w;
}e[maxn];
int dist[maxn],vis[maxn];
void add(int u,int v,int w)
{
	cnt++;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	e[cnt].v=v;
	head[u]=cnt;
}
bool spfa(int s)
{
	queue<int>p;
	memset(dist,0X3F,sizeof(dist));
	dist[0]=0;
	vis[0]=1;
	p.push(0);
	while(p.size())
	{
		
		int u=p.front();
		vis[u]=0;
		p.pop();
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(dist[v]>dist[u]+e[i].w)
			{
				dist[v]=dist[u]+e[i].w;
				if(!vis[v])
				{
					tot[v]++;
					vis[v]=1;
					if(tot[v]==n+1) return 0; 
					p.push(v);
				}
			}
		}
	}
	return 1;
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) add(0,i,0);
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		cin>>x>>y>>z;
		add(y,x,z);
	}
	if(!spfa(0)) cout<<"NO";
	else
	{
		for(int i=1;i<=n;i++) cout<<dist[i]<<' ';
	}
	return 0;
}

P3371 【模板】单源最短路径（弱化版）

Problem Link

solution

\(\quad\)最短路板题

code

#include<iostream>
#include<cstring>
#include<queue>
#define maxn 100001
#define maxm maxn*2+10
#define inf 2147483647
using namespace std;
priority_queue<pair<int,int> > q;
unsigned long long dist[maxn+1];
bool vist[maxn+1];
int n,m,s;
int u,v,w;
int nbs[maxn+1],nxt[maxm+1],ev[maxm+1],ew[maxm+1];
void dijkstra(int src)
{
    memset(dist,0X3F,sizeof(dist));
    //for(int i=1; i<=n; i++) dist[i]=inf;
    memset(vist,0,sizeof(vist));
    dist[src]=0;
    q.push(make_pair(0,src));
    while(1)
    {
        int u=q.top().second;
        q.pop();
        if(vist[u]) return ;
        if(u==0) return ;
        vist[u]=1;
        for(int j=nbs[u];j!=0; j=nxt[j])
        {
            //cout<<"aa";
            int v=ev[j];
            if(vist[v]==0 && dist[u]+ew[j]<dist[v])
            {
                dist[v]=dist[u]+ew[j];
                q.push(make_pair(-dist[v],v));
            }
        }
    }
}
int main()
{
    int te;
    cin>>n>>m>>s;
    memset(nbs,0,sizeof(nbs));
    for(int i=1; i<=m; i++)
    {
        cin>>u>>v>>w;
        int p=i;
    nxt[p] = nbs[u];
    nbs[u] = p;
    ev[p] = v;
    ew[p] = w;
    }
    dijkstra(s);
    for(int i=1;i<=n;i++) cout<<dist[i]<<' ';
    return 0;
}

P4568 [JLOI2011]飞行路线

Problem Link

solution

\(\quad\)分层图板题

code

#include<bits/stdc++.h>
using namespace std;
struct edge
{
	int v,w,nxt;
}e[3001001];
int cnt,head[3001001];
void add(int u,int v,int w)
{
	cnt++;
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
int dis[3001001];
bool vis[3001001];
struct node
{
	int id,dis;
	bool operator < (const node &tt) const
	{
		return dis>tt.dis;
	}
};
priority_queue<node> q;
void dij(int s)
{
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	q.push(node{s,0});
	while(q.size())
	{
		node uu=q.top();
		int u=uu.id;
		q.pop();
		if(vis[u]) continue ;
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				q.push(node{v,dis[v]});
			}
		}
	}
}
int n,m,k,s,t;
int main()
{
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	for(int i=0;i<m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
		for(int j=1;j<=k;j++)
		{
			add(u+(j-1)*n,v+j*n,0);
			add(v+(j-1)*n,u+j*n,0);
			add(u+j*n,v+j*n,w);
			add(v+j*n,u+j*n,w);
		}
	}
	for(int i=1;i<=k;i++)
	{
		add(t+(i-1)*n,t+i*n,0);
	}
	dij(s);
	printf("%d",dis[t+k*n]);
	return 0;
}

P1983 [NOIP2013 普及组] 车站分级

Problem Link

solution

\(\quad\)停靠的车一定比不停靠的车的级别要高，那么就让等级高的点向等级低的点连一条长度为 1 的有向边。那么答案就是这个图的最长连的长度+1

\(\quad\)那么先按拓扑排序分层，再 dp 转移。

优化

\(\quad\)因为连的边太多了，可以设一些虚拟节点。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,s,uans[100010],st[100010],to[2010][1010],ans,a[100010];
void dfs(int u)
{
	if(uans[u]) return ;
	for(int i=1;i<=to[u][0];i++)
	{
		if(!uans[to[u][i]]) dfs(to[u][i]);
		uans[u]=max(uans[u],uans[to[u][i]]+1);
	}
	if(u>n) uans[u]--;
	ans=max(ans,uans[u]);
}
int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		cin>>s;
		for(int j=1;j<=s;j++) cin>>a[j],st[a[j]]=i,to[n+i][++to[n+i][0]]=a[j];
		for(int u=a[1]+1;u<a[s];u++)
		if(st[u]!=i) to[u][++to[u][0]]=n+i;
	}
	for(int i=1;i<=n;i++)
	if(!uans[i]) dfs(i);
	cout<<(++ans)<<endl;
	return 0;
}

P4017 最大食物链计数

Problem Link

solution

\(\quad\)拓扑排序

code

#include<bits/stdc++.h>

#define int long long
using namespace std;
const int maxn = 5001, mod = 80112002;
int n, m, ind[maxn], oud[maxn], res, ans[maxn];
queue<int> q;
vector<int> e[maxn];

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        e[a].push_back(b);
        ind[b]++;
        oud[a]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!ind[i]) {
            ans[i] = 1;
            q.push(i);
        }
    }
    while (q.size()) {
        int u = q.front();
        q.pop();
        for (int i = 0; i < e[u].size(); i++) {
            int v = e[u][i];
            ind[v]--;
            if (!ind[v]) q.push(v);
            ans[v] = (ans[v] + ans[u]) % mod;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (!oud[i]) {
            res += ans[i];
            res %= mod;
        }
    }
    cout << res << endl;
    return 0;
}

P1113 杂务

Problem Link

solution

\(\quad\)这是一个拓扑排序的裸题，不过多赘述。

code

#include <bits/stdc++.h>

using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

const int N = 500005;

int ind[N], f[N], a[N];
vector<int> edge[N];
queue<int> q;

int main() {
    int n = read();
    for (int i = 1; i <= n; i++) {
        int x = read();
        a[i] = read();
        while (int y = read()) {
            if (!y) break;
            edge[y].push_back(x);
            ind[x]++;
        }
    }
    for (int i = 1; i <= n; i++) {
        if (ind[i] == 0) {
            q.push(i);
            f[i] = a[i];
        }
    };
    while (!q.empty()) {
        int rhs = q.front();
        q.pop();
        for (int i = 0; i < edge[rhs].size(); i++) {
            int u = edge[rhs][i];
            ind[u]--;
            if (ind[u] == 0) q.push(u);
            f[u] = max(f[u], f[rhs] + a[u]);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, f[i]);
    }
    printf("%d\n", ans);
    return 0;
}

P3916 图的遍历

Problem Link

solution

\(\quad\)这个题目有两个做法：

$\quad\(1. 反向建边 + dfs（也就是考虑每一个较大的编号能到达哪些编号） \)\quad$2. 缩点 + dp

code

#include<bits/stdc++.h>

using namespace std;

#define MAXL 100010

int N, M, A[MAXL];
vector<int> G[MAXL]; 

void dfs(int x, int d) {
	if(A[x]) return; 
	A[x] = d;
	for(int i=0; i<G[x].size(); i++)
		dfs(G[x][i], d);
}

int main() {
	int u, v;
	scanf("%d%d", &N, &M);
	for(int i=1; i<=M; i++) {
		scanf("%d%d", &u, &v);
		G[v].push_back(u);
	}
	for(int i=N; i; i--) dfs(i, i); 
	for(int i=1; i<=N; i++) printf("%d ", A[i]);
	printf("\n");
	return 0;
}

P5318 【深基18.例3】查找文献

Problem Link

solution

\(\quad\)最基本的搜索，因为要排序，拿 vector 存会比较好。

code

#include<bits/stdc++.h>

using namespace std;
struct edge {
    int u, v;
};
vector<int> e[100001];
vector<edge> s;
bool vis1[100001] = {0}, vis2[100001] = {0};
bool cmp(edge x, edge y) {
    if (x.v == y.v)
        return x.u < y.u;
    else return x.v < y.v;
}

void dfs(int x) {
    vis1[x] = 1;
    cout << x << " ";
    for (int i = 0; i < e[x].size(); i++) {
        int point = s[e[x][i]].v;
        if (!vis1[point]) {
            dfs(point);
        }
    }
}

void bfs(int x) {
    queue<int> q;
    q.push(x);
    cout << x << " ";
    vis2[x] = 1;
    while (!q.empty()) {
        int fro = q.front();
        for (int i = 0; i < e[fro].size(); i++) {
            int point = s[e[fro][i]].v;
            if (!vis2[point]) {
                q.push(point);
                cout << point << " ";
                vis2[point] = 1;
            }
        }
        q.pop();
    }
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int uu, vv;
        cin >> uu >> vv;
        s.push_back((edge) {uu, vv});
    }
    sort(s.begin(), s.end(), cmp);
    for (int i = 0; i < m; i++)
        e[s[i].u].push_back(i);
    dfs(1);
    cout << endl;
    bfs(1);
}

这篇关于【准备5】基础图论问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！