CSP图论题

发表于 分类于
ccf-csp简单图论题解

csp201609-4 交通规划

题意：求点1到其他点的最短路

第一眼看上去是求最小生成树，但其实是求点1到其他点的最短路
只需要利用cost[]数组记录最短路上边的权值即可
但是对一个点v来说存在多条最短路的时候，cost[v]保存到v的边的最小的权值

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <stack>
#include <ctime>
using namespace std;
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define MS(a,b) memset(a,b,sizeof(a))
#define swap(a,b) a^=b^=a^=b
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e4 + 10;
const LL modd = 1e6;
int n, m, dis[MAXN], cost[MAXN];
vector<P> G[MAXN];
void spfa(int src){
	MS(dis,INF);
	MS(cost,INF);
	priority_queue<P,vector<P>,greater<P> > que;
	dis[src] = 0;
	que.push(P(dis[src],src));
	while(!que.empty()){
		P t = que.top(); que.pop();
		int u = t.second, d = t.first;
		if(dis[u] < d)continue;
		REP(i,0,G[u].size()){
			int v = G[u][i].first, w = G[u][i].second;
			if(dis[v] > d + w){
				cost[v] = w;
				dis[v] = d + w;
				que.push(P(dis[v],v));
			}else if(dis[v] == d + w){
				cost[v] = min(cost[v],w);
				que.push(P(dis[v],v));
			}
		}
	}
	return ;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int a, b, c;
    cin >> n >> m;
	REP(i,0,m){
		cin >> a >> b >> c;
		G[a].push_back(P(b,c));
		G[b].push_back(P(a,c));
	}
	spfa(1);
	LL ans = 0;
	REP(i,2,n+1) ans += cost[i];
	cout << ans << endl;
    return 0;
}

csp201604-4 游戏

题意：求（1，1) 到 （n，m） 的最短路

只需要利用bfs来搜索权值为1的最短路
但要利用vis[x][y][t]来记录点（x,y）在时间t是否可以访问

#include <bits/stdc++.h>

using namespace std;
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define MS(a,b) memset(a,b,sizeof(a))
#define swap(a,b) a^=b^=a^=b
#define ls (rt<<1)
#define rs (rt<<1|1)
#define mid ((l+r)>>1)
#define READ3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define READ4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define lson l,mid,ls
#define rson (mid+1),r,rs
typedef pair<int,int> P;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 1e2 + 10;
const long double PI = acos(-1.0);
const LL modd = 1e6;
int n, m, t, dir[][2] = {0,1,-1,0,1,0,0,-1};
int G[MAXN][MAXN];
bool vis[MAXN][MAXN][500];
int bfs(int ex, int ey){
    queue<P> que;
    que.push(P(0,1*1000+1));
    vis[1][1][0] = true;
    while(!que.empty()){
        P t = que.front(); que.pop();
        int x = t.second/1000, y = t.second%1000, step = t.first;
        // if(vis[x][y][step]) continue; vis[x][y][step] = true;
        if(x == ex && y == ey) return step;
        REP(i,0,4){
            int xx = x + dir[i][0], yy = y + dir[i][1], nextstep = step + 1;
            int s = G[xx][yy]/1000, e = G[xx][yy]%1000;
            if(xx < 1 || yy < 1 || xx > n || yy > m || G[xx][yy] != 0 && nextstep >= s && nextstep <= e || vis[xx][yy][nextstep]) continue;
            que.push(P(nextstep,xx*1000+yy));
            vis[xx][yy][nextstep] = true;
        }
    }
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    MS(G,0);
    MS(vis,0);
    cin >> n >> m >> t;
    int a, b, s, e;
    REP(i,0,t){
        cin >> a >> b >> s >> e;
        G[a][b] = s*1000+e;
    }
    cout << bfs(n,m) << endl;
    return 0;
}

csp201512-4 送货

题意：求从点1出发到点n的欧拉路

只需要记录每个点的入度、出度，来判断是否存在以点1为起点的欧拉路
如果存在欧拉路输出路径，否则输出-1
输出路径，不要用dfs，用栈来模拟dfs,否则会爆栈

无向图

  • 一个无向图 G 存在欧拉路径当且仅当无向图 G 是连通图， 且该图中有两个奇度顶点（度数为奇
    数） 或者无奇度顶点。
  • 当无向图 G 是包含两个奇度顶点的连通图时， G 的欧拉路径必定以这两个奇度顶点为端点。
  • 一个无向图 G 存在欧拉回路当且仅当无向图 G 连通且不存在奇度顶点。

有向图

  • 一个有向图 G 存在欧拉路径当且仅当 G 是连通的有向图， 且满足以下两个条件之一：
    所有顶点的入度和出度相等；
    有一个顶点的出度与入度之差为 1 ， 一个顶点的出度与入度之差为 -1 ， 其余顶
    点的入度和出度相等。
  • 当有向图 G 包含两个入度和出度不相同的顶点且有欧拉路径时， 欧拉路径必定以这两个入度出
    度不相同的顶点为端点。
  • 一个有向图 G 存在欧拉回路当且仅当图 G 是连通的有向图， 且所有顶点的入度和出度相等。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <cmath>
#include <stack>
using namespace std;
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define MS(a,b) memset(a,b,sizeof(a))
#define READ(a) scanf("%d",&a)
#define READ2(a,b) scanf("%d%d",&a,&b)
#define READ3(a,b,c) scanf("%d%d%d",&a,&b,&c)
typedef pair<int,int> P;
typedef long long LL;
const int MAXN = 1e4 + 10;
const int MAXL = 1e3 + 10;
bool vis[MAXN][MAXN];
int n, m, f[MAXN], siz[MAXN];
void init(){MS(vis,0);REP(i,0,MAXN)f[i] = i, siz[i] = 1;}
int find(int x){return f[x] == x? x: f[x] = find(f[x]);}
void merge(int a, int b){ a=find(a);b=find(b);if(a!=b){f[a]=b;siz[b]+=siz[a];}}
set<int> G[MAXN];
stack<int> stk;
void dfs(int u){
	stack<int> d;
	d.push(u);
	while(!d.empty()){
		int u = d.top();
		bool ok = false;
		for(set<int>::iterator it = G[u].begin(); it != G[u].end(); it++){
			int v = *it;
			if(vis[u][v]) continue; vis[u][v] = vis[v][u] = true;
			d.push(v);
			ok = true;
			break;
		}
		if(!ok) {
			d.pop();
			stk.push(u);
		}
	}
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in","r",stdin);
    freopen("out","w",stdout);
#endif
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	init();
	bool ok = false;
	cin >> n >> m;
	int a, b;
	REP(i,0,m){
		cin >> a >> b;
		G[a].insert(b);
		G[b].insert(a);
		merge(a,b);
	}
	if(siz[find(a)] == n){
		int num = 0;
		REP(i,1,n+1)  if(int(G[i].size())%2 != 0)num++;
		if(num == 2 && int(G[1].size())%2 != 0 || num == 0) {
			ok = true;
			dfs(1);
			cout << 1;
			stk.pop();
			while(!stk.empty()) {
				cout << ' ' << stk.top();
				stk.pop();
			}
			cout << endl;
		}
	}
	if(!ok) cout << -1 << endl;
	return 0;
}

csp201509-4 高速公路

题意：给图G<V,E> 求其中两点双向可达的点队数

先利用tarjan求出强联通分量的个数scc,每个强联通分量中包含的点的个数siz[]
一个强连通分量v中，任意两点都互相可达，两点双向可达的点队数为 siz[v]*siz[v]/2
对每个强连通分量中的两点可达的点队数求和即可

[Code] losing
代码丢了，放个模板

void tarjan(int u,int fa)  {  
    int cnt = 0;//统计u的孩子个数
    low[u] = dfn[u] = ++idx;  
    for(int i = 0; i < G[u].size(); i++){  
        int v = G[u][i];  
        if(v == fa) continue;  
        if(!dfn[v]){  
            tarjan(v,u);  
            ++cnt;  
            low[u] = min(low[u],low[v]);  
            if((root != u && dfn[u] <= low[v]) || (root == u && cnt > 1)) 
//判断是否是割点  
                isap[u] = 1;  
            if(dfn[u] < low[v]) cutE[++numE]=Edge(u,v);
//判断是否是桥,视具体情况采用恰当的结构记录。  
        }  
        else low[u] = min(low[u],dfn[v]);//这里不用判断是否点v在栈中  
    }  
}

csp201503-4 网络延时

题意：求树上任意两点的距离中最大的距离

这道题就是求树的直径，两次bfs即可

树的直径求法：

第一次任意选一个点进行dfs(bfs)找到离它最远的点，此点就是最长路的一个端点，再以此点进行dfs（bfs），找到离它最远的点，此点就是最长路的另一个端点，于是就找到了树的直径。

证明：略

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <stack>
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define MS(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef long long LL;
typedef pair<int,LL> P;
const int MAXN = 2e4 + 10;
const int INF = 0x3f3f3f3f;
vector<int> G[MAXN];
bool vis[MAXN];
int n, m;
LL bfs(int &src){
	MS(vis,0);
	LL ret = 0;
	vis[src] = true;
	queue<P> que;
	que.push(P(0,src));
	while(!que.empty()){
		P t = que.front(); que.pop();
		int u = t.second;
		LL step = t.first;
		ret = step;
		src = u;
		REP(i,0,G[u].size()){
			int v = G[u][i];
			if(!vis[v]) {
				vis[v] = true;
				que.push(P(step+1,v));
			}
		}

	}
	return ret;
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int t;
    cin >> n >> m;
    REP(i, 2, n + 1) {
        cin >> t;
        G[t].push_back(i);
		G[i].push_back(t);
    }
    REP(i, 1, m + 1) {
        cin >> t;
        G[t].push_back(i + n);
		G[i + n].push_back(t);
    }
	int src = 1;
	bfs(src);
	cout << bfs(src) << endl;
    return 0;
}

csp201412-4 最优灌溉

题意：求最小生成树

最小生成树摸板题
利用kruskal求即可

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <queue>
using namespace std;
#define REP(i,a,b) for(int i = (a); i < (b); ++i)
#define MS(a,b) memset(a,b,sizeof(a))
typedef long long LL;
typedef pair<int,int> P;
const int MAXN = 2e3 + 10;
const int MAXM = 1e5 + 10;
const int INF = 0x3f3f3f3f;
class edge{
public:
	int u, v, cost;
	bool operator < (const edge &b)const{
		return cost < b.cost;
	}
};
int n, m, f[MAXN];
edge dat[MAXM];
void init(){REP(i,0,MAXN)f[i] = i;}
int find(int x){return f[x] == x? x: f[x]=find(f[x]);}
void merge(int a, int b){ a=find(a),b=find(b);if(a != b)f[a] = b;}
LL kru(){
	init();
	LL ret = 0;
	for(int i = 0, res = n; i < m && res > 1; i++){
		int u = dat[i].u, v = dat[i].v, cost = dat[i].cost;
		if(find(u) != find(v)){
			merge(u,v);
			ret += (LL)cost;
		}
	}
	return ret;
}
int main(){
#ifdef QLOCAL
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
#endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m;
	REP(i,0,m)
		cin >> dat[i].u >> dat[i].v >> dat[i].cost;
	sort(dat,dat+m);
	cout << kru() << endl;
	return 0;
}

csp201403-4 无线网络

题意： 求点1到点n的最少经过的点

先把n个坐标点中，两点距离小于r的点连边，转换成图G<V,E>
再把点权下方的边权，即dis[n]-1 d代表到 1-n中经过的点的数量

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <queue>
#include <map>
#include <vector>
#include <set>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <stack>
#include <ctime>
using namespace std;
#define REP(i,a,b) for(int i = (a); i < (b); i++)
#define MS(a,b) memset(a,b,sizeof(a))
#define READ2(a,b) scanf("%d%d",&a,&b)
#define READ3(a,b,c) scanf("%d%d%d",&a,&b,&c)
typedef pair<int,int> P;
typedef long long LL;
const int MAXN = 1e3 + 10;
const int INF = 0x3f3f3f3f;
const int MAXL = 1e3 + 10;
P dat[MAXN];
int n, m, k, r, dis[MAXN];
vector<int> G[MAXN];
class node{
public:
	int first,second,cnt;
	node(int a, int b, int c):first(a),second(b),cnt(c){}
	bool operator < (const node &b)const{
		return first > b.first;	
	}
};
void spfa(int src){
	MS(dis,INF);
	priority_queue<node> que;
	dis[src] = 0;
	que.push(node(0,src,0));
	while(!que.empty()){
		node t = que.top();que.pop();
		int u = t.second, d = t.first, cnt = t.cnt;
		if(dis[u] < d)continue;
		REP(i,0,G[u].size()){
			int v = G[u][i], w = 1;
			if(dis[v] > d + w && cnt + (v >= n) <= k){
				dis[v] = d + w;
				que.push(node(dis[v],v,cnt+(v>=n)));
			}
		}
	}
}
inline LL getDis(P a, P b){
	return (LL)(a.first-b.first)*(a.first-b.first)+(LL)(a.second-b.second)*(a.second-b.second);
}
int main() {
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
#endif
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n >> m >> k >> r;
	int cnt = n + m;
	REP(i,0,n) cin >> dat[i].first >> dat[i].second;
	REP(i,n,cnt) cin >> dat[i].first >> dat[i].second;
	REP(i,0,cnt)
		REP(j,i+1,cnt)
			if(getDis(dat[i],dat[j]) <= (LL)r*r){
				G[i+1].push_back(j+1);
				G[j+1].push_back(i+1);
			}
	spfa(1);
	cout << dis[2] - 1 <<endl;
	return 0;
}

祝大家CCF-CSP考个好成绩！