搜索与图论

· 2021-11-29 · # 学习笔记

DFS与BFS

注意剪枝，边界表示。
状态需要判重时，能不用map尽量不用，能用数字尽量不用字符串

树与图的遍历

正常遍历
拓扑排序：根据入度删点，入度为0的点加入队列bfs

最短路

floyd & spfa & dijkstra

spfa：队头出队，松弛它的边，松弛了且不在队内的点入队。

判断负环：判入队次数是否>n

差分约束：按照 $dis[v] <= dis[u] + w$ 的形式建边求最短路或反之求最长路即可

差分约束最优解最大值求最短路最小值求最长路

dij：每次取出当前距离最小的点，表示该点的最短路已经确定。

反向建边
虚点建边

最小生成树

prim
kruskal
次小生成树？

prim维护f[i][j] 表示最小生成树中 i到j 的最长边

kruscal + lca O(1)离线查询 i到j 的最长边

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
#define lowbit(x) (x&-x)
#define LOCAL
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
inline int  Rem() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
inline void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
inline void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
/**/
const int inf = 0x3f3f3f3f;
const int N = 105;
int t,n,m,e[N][N],cnt,dis[N],s1,s2,pre[N],f[N][N];
bool tree[N][N], vis[N];
struct edge
{
	int from,to,w;
}ed[N*N];
/**/
int main()
{
	#if ONLINE_JUDGE
	#else
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
	#endif
	read(t);
	while(t--)
	{
		cnt = 0;
		read(n);read(m);
		for(int i=1;i<=n;i++)
		{
			pre[i] = 0;
			for(int j=1;j<=i+1;j++) e[i][j] = e[j][i] = inf, tree[i][j] = tree[j][i] = 0, f[i][j] = f[j][i] = 0;
		}
		for(int i=1,a,b,c;i<=m;i++)
		{
			read(a);read(b);read(c);
			ed[++cnt] = (edge){a,b,c};
			e[a][b] = e[b][a] = c;
		}
		for(int i=0;i<=n;i++) dis[i] = inf, vis[i] = 0;
		dis[1] = 0;
		s1 = 0;
		for(int i=1;i<=n;i++)
		{
			int u = 0;
			for(int j=1;j<=n;j++) if(!vis[j]&&dis[j]<dis[u]) u = j;
			vis[u] = 1;
			tree[pre[u]][u] = tree[u][pre[u]] = 1;
			if(u) s1 += dis[u];
			for(int j=1;j<=n;j++)
			{
				if(u==j) continue;
				if(vis[j])
				{
					f[j][u] = f[u][j] = max(f[pre[u]][j], dis[u]);
				}
				if(!vis[j] && dis[j] > e[u][j])
				{
					dis[j] = e[u][j];
					pre[j] = u;
				}
			}
		}
		s2 = inf;
		for(int i=1;i<=cnt;i++)
		{
			int u = ed[i].from, v = ed[i].to;
			if(tree[u][v]) continue;
			// printf("%d - %d = %d\n",u,v,f[u][v]);
			s2 = min(s2, s1 - f[u][v] + ed[i].w);
		}
		cout << s1 <<' '<< s2 <<'\n';
	}
	return 0;
}

有向图有根最小生成树？ -> 朱刘算法

#include <iostream>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#define ll long long
#define space putchar(' ')
#define endl putchar('\n')
#define debug puts("------------------------")
#define lowbit(x) (x&-x)
#define LOCAL
using namespace std;
inline void read(int &a) {a=0;int c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();a*=b; }
inline int  Rem() {int a=0,c=getchar(),b=1; while(c>'9'||c<'0') {if(c=='-')b=-1;c=getchar();} while(c>='0'&&c<='9') a=(a<<3)+(a<<1)+c-48,c=getchar();return a*=b; }
inline void write(int x) {if(x>9)write(x/10);putchar('0'+x%10);}
inline void W(int x) {if(x<0){putchar('-'),x=-x;}write(x);}
/**/
const int N = 105, M = 1e4 + 5;
int n, cnt, m, fa[N], id[N], vis[N];
double x[N], y[N], in[N];
struct edge
{
   int from, to;
   double w;
}e[M];
/**/
inline double get(int i, int j)
{
   return sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));
}
inline double zhuliu()
{
   double ans = 0;
   int root = 1;
   while(1)
   {
   	for(int i = 1; i <= n; i++) in[i] = 0x3f3f3f3f;
   	for(int i = 1; i <= cnt; i++)
   	{
   		int u = e[i].from, v = e[i].to;
   		if(u != v && e[i].w < in[v])
   		{
   			fa[v] = u;
   			in[v] = e[i].w;
   		}
   	}
   	for(int i = 1; i <= n; i++) if(in[i] == 0x3f3f3f3f) return -1;
   	int tot = 0;
   	in[root] = 0;
   	for(int i = 1; i <= n; i++) vis[i] = id[i] = 0;
   	for(int i = 1; i <= n; i++)
   	{
   		int u = i;
   		ans += in[u];
   		while(vis[u] != i && !id[u] && u != root) vis[u] = i, u = fa[u];
   		if(u != root && !id[u])
   		{
   			id[u] = ++tot;
   			for(int x = fa[u]; x != u; x = fa[x]) id[x] = tot;
   		}
   	}
   	if(!tot) break;
   	for(int i = 1; i <= n; i++) if(!id[i]) id[i] = ++tot;
   	int cnt_ = 0;
   	for(int i = 1; i <= cnt; i++)
   	{
   		int u = e[i].from, v = e[i].to;
   		if(id[u] =! id[v]) e[++cnt_] = (edge){id[u], id[v], e[i].w - in[v]};
   	}
   	cnt = cnt_;
   	n = tot;
   	root = id[root];
   }
   return ans;
}
int main()
{
   #if ONLINE_JUDGE
   #else
   freopen("test.in","r",stdin);
   freopen("test.out","w",stdout);
   #endif
   while(cin >> n >> m)
   {
   	cnt = 0;
   	for(int i = 1; i <= n; i++)
   	{
   		cin >> x[i] >> y[i];
   	}
   	for(int i = 1, a, b; i <= m; i++)
   	{
   		read(a); read(b); e[++cnt] = (edge){a, b, get(a, b)};
   	}
   	double ans = zhuliu();
   	if(ans == -1) puts("poor snoopy");
   	else printf("%.2f\n", ans);
   }
   return 0;
}

二分图：

待补习