图论

2018-08-21

字数统计: 2.2k字 | 阅读时长: 12min

一.算法

1.一笔画问题

2.拓扑排序

3.最小生成树

4.最短路径

5.有向图的强连通分量

6.无向图的双连通分量、割点与桥

二.题目

混合图

你有一个混合图，它有n 个顶点，m 条边，其中a 条是有向边，b条是无向边。现在要求为这b 条无向边确定一个方向，使得最后的有向图上不存在环。
1 ≤ n, a, b ≤ 105, m = a + b。
不用考虑无解的情况。

输出两个数u,v表示无向边（u,v）方向为由u指向v。

输入：

8 8 2
1 2
1 3
2 3
3 7
7 8
2 4
4 5
4 6
1 3
2 7

输出：

1 3
2 7

#include<bits/stdc++.h>
using namespace std;
int n,m1,m2,to[110000],in[110000];
struct node
{
	int ne,to;
}edge[10001000];
int head[110000],cnt;
void add(int u,int v)
{
	edge[++cnt].ne=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}
int ans[110000],tot;
void topu()
{
	queue<int> q;
	for(int i=1;i<=n;i++) if(!in[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		ans[++tot]=u;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to;
			in[v]--;
			if(!in[v]) q.push(v);
		}
	}
}
int main()
{
	scanf("%d %d %d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		add(u,v);
		in[v]++;
	}
	for(int i=1;i<=m2;i++)
	{
		int u,v;
		scanf("%d %d",&u,&v);
		to[u]=v;
		to[v]=u;
	}
	topu();
	for(int i=1;i<=tot;i++)
	if(to[i]) printf("%d %d\n",i,to[i]),to[to[i]]=0;
	return 0;
}

题解：

既然要求最后的有向图没有环，也就是要求最后是个DAG。
DAG 进行拓扑排序后边的方向都是拓扑序小的连向拓扑序大的。
先把无向边忽略，对图进行拓扑排序，最后无向边的方向就是拓扑
序小的连向拓扑序大的。

灾后重建

#include<bits/stdc++.h>
using namespace std;
int n,m,t[210];
int dis[210][210],k;
void floyd(int ti)
{
	while(t[k]<=ti&&k<n)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
		k++;
	}
	
}
int main()
{
	scanf("%d %d ",&n,&m);
	memset(dis,0x3f,sizeof(dis));//1061109567
	for(int i=0;i<n;i++)
	scanf("%d",&t[i]),dis[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		int u,v,wi;
		scanf("%d %d %d",&u,&v,&wi);
		dis[u][v]=dis[v][u]=wi;
	}
	int opt;
	scanf("%d",&opt);
	for(int i=1;i<=opt;i++)
	{
		int x,y,ti;
		scanf("%d %d %d",&x,&y,&ti);
		floyd(ti); 
		if(dis[x][y]==0x3f3f3f3f||t[x]>ti||t[y]>ti) printf("-1\n");
		else printf("%d\n",dis[x][y]);
	}
	return 0;
}

这道题刷新了我对floyd算法的看法，原来它还可以这样用。。。
这道题核心只有一句话：因为每一个村庄建好的时间和询问保证时间是不下降的，所以每一个村庄重建好，就用当前建好的村庄更新dis，然后输出。

chess

#include<bits/stdc++.h>
using namespace std;
struct node
{
	long long x,y,h;
}chess[21][1001];
int fa[10001];
int getfa(int x)
{
	return (x==fa[x])?x:fa[x]=getfa(fa[x]);
}
bool cmp(node a,node b)
{
	return a.h<b.h;
}
long double getdis(int i,int k,int j)
{
	long long x=abs(chess[j][i].x-chess[j][k].x);
	long long y=abs(chess[j][i].y-chess[j][k].y);
	long long h=abs(chess[j][i].h-chess[j][k].h);
	return sqrt(x*x+y*y+h*h);
}
int main()
{
	int T;
	scanf("%d",&T);
	for(int j=1;j<=T;j++)
	{
		bool tag=0;
		long long h,r;
		int n,s=0,t;
		scanf("%d %lld %lld",&n,&h,&r);
		t=n+1;
		for(int i=1;i<=n;i++)
		scanf("%lld %lld %lld",&chess[j][i].x,&chess[j][i].y,&chess[j][i].h),fa[i]=i;
		fa[t]=t;
		sort(chess[j]+1,chess[j]+1+n,cmp);
		for(int i=1;i<=n;i++) if(chess[j][i].h<=r) fa[i]=s;
		
		for(int i=1;i<=n;i++)
			for(int k=i+1;k<=n;k++)
				if(getdis(i,k,j)<=(long double)2*r)
				{
					int f1=getfa(k);
					int f2=getfa(i);
					if(f1>f2) fa[f1]=f2;
				}
		for(int i=1;i<=n;i++)
		{
			if(chess[j][i].h+r>=h) fa[t]=getfa(i);
			if(fa[t]==s)
			{
				printf("Yes\n");
				tag=1;
				break;
			} 
		}
		if(!tag) printf("No\n");
	}
	return 0;
}

[poj3159] candies

差分约束。。。

#include<queue>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int n,m;
struct node
{
	int ne,to,w;
}edge[150001];
int head[30001],cnt;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}
int dis[30001],vis[30001];
void dj(int s)
{
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	q.push(make_pair(0,s));
	dis[1]=0;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	dj(1);
	printf("%d",dis[n]);
	return 0;
}

飞行路线

#include<bits/stdc++.h>
using namespace std;
int n,m,k,s,t;
struct node
{
	int ne,to,w;
}edge[1100000];
int head[110000],cnt;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].w=w;
	edge[cnt].ne=head[u];
	head[u]=cnt;
}
int dis[110000][15],vis[110000];
void dijkstra(int s)
{
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	q.push(make_pair(0,s));
	for(int i=0;i<=k;i++)
	dis[s][i]=0;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			for(int j=0;j<=k;j++)
			{
				if(dis[v][j]>dis[u][j]+w||(j+1<=k&&dis[v][j]>dis[u][j+1]))
				{
					if(j+1<=k) dis[v][j]=min(dis[u][j+1],dis[u][j]+w);
					else dis[v][j]=dis[u][j]+w; 
					if(!vis[v])
					{
						q.push(make_pair(dis[v][j],v));
					}
				}
			}
		}
	}
}
int main()
{
	scanf("%d %d %d",&n,&m,&k);
	scanf("%d %d",&s,&t);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	dijkstra(s);
	printf("%d",dis[t][0]);
	return 0;
}

这道题卡spfa,qwq.我的spfa只拿了90分，一个数据点RE，改为dijkstra之后快了一倍。
但由于我选择在dijkstra枚举k,来更新答案所以一个点许多次出现。所以vis[]需要记录一个点出现的次数。
最坏情况下，一个点需要更新n个点，所以vis[i]==n时continue;

其实还可以将一个点分为n*k+1个点，用(i,k)表示，每次更新(n,k+1)和(n,k);
以下引用大佬代码：
出处：

大佬博客

#include <iostream>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#define inc(i) (++ i)
#define dec(i) (-- i)
using namespace std;

const int N = 10000 + 7 , K = 20 + 2 , M = 50000 + 7;
int n , m , k , Dis[N][K] , S , E;
int Head[N] , Node[M << 1] , Next[M << 1] , W[M << 1] , tot = 1;
bool inq[N][K];
struct Node_1
{
    int u , k , w;
    bool operator < (const Node_1& a)const//优先队列套上结构体判断语句需要打const
    {
        return w > a.w;
    }
};
priority_queue <Node_1> Q;

inline void Add(int u , int v , int w)
{
    Next[inc(tot)] = Head[u] , Head[u] = tot , W[tot] = w , Node[tot] = v;
    Next[inc(tot)] = Head[v] , Head[v] = tot , W[tot] = w , Node[tot] = u;
}

inline void Dij(int S)
{
    memset(Dis , 127 / 3 , sizeof(Dis));
    Node_1 u;
    Dis[S][0] = 0 , Q.push(Node_1{S , 0 , 0}) , inq[S][0] = 1;
    int v;
    while(!Q.empty())
    {
        u = Q.top() , Q.pop() , inq[u.u][u.k] = 0;
        for(int i = Head[u.u] ; i ; i = Next[i])
        {
            v = Node[i];
            if(Dis[v][u.k] > Dis[u.u][u.k] + W[i])
            {
                Dis[v][u.k] = Dis[u.u][u.k] + W[i];
                if(!inq[v][u.k]) Q.push(Node_1{v , u.k , Dis[v][u.k]}) , inq[v][u.k] = 1;
            }
            if(u.k + 1 <= k) 
                if(Dis[v][u.k + 1] > Dis[u.u][u.k])
                {
                    Dis[v][u.k + 1] = Dis[u.u][u.k];
                    if(!inq[v][u.k + 1]) Q.push(Node_1{v , u.k + 1 , Dis[v][u.k + 1]}) , inq[v][u.k + 1] = 1;
                }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    cin >> S >> E;
    for(int i = 1 , u , v , w ; i <= m ; inc(i))    cin >> u >> v >> w , Add(u + 1 , v + 1 , w);
    Dij(S + 1);
    int Ans = Dis[0][0];
    for(int i = 0 ; i <= k ; inc(i))
        Ans = min(Ans , Dis[E + 1][i]);
    printf("%d" , Ans);
    return 0;
}

链接之前的博客（里面有这道题的分层图代码）

在博客最下面

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/10f14ed7.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！