图论总结
DFS
套路1：
构造的时候选一颗DFS树忽略其他边进行构造，
（对于点标和度数奇偶性的问题，假如所有的点的度数和为偶数的话，则成立）
套路2：
对于一个无向图求出一棵DFS树，然后每条非树边对应了一个环（每条非树边必然连向祖先）
例题：$$Xor$$和仙人掌判定(改点到祖先在树的路径)。
//dfs树+树形DP
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 500010
#define M 1000010
#define P 998244353
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int T,n,m,p[N],f[N],size[N],fac[N],inv[N],inv2[N],fa[N],from[N],deep[N],t;
bool flag[N];
struct data{int to,nxt,op;
}edge[M<<1];
void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].op=0,p[x]=t;}
void inc(int &x,int y){x+=y;if (x>=P) x-=P;}
int C(int n,int m){return 1ll*fac[n]*inv[m]%P*inv[n-m]%P;}
int calc(int n,int m){return 1ll*C(n,2*m)*C(2*m,m)%P*fac[m]%P*inv2[m]%P;}
void dfs(int k)
{
flag[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (!flag[edge[i].to]&&!edge[i].op)
{
size[k]++;
dfs(edge[i].to);
int s=0;
for (int j=0;j<=(size[edge[i].to]>>1);j++)
inc(s,1ll*calc(size[edge[i].to],j)*(size[edge[i].to]-(j<<1)+1)%P);
f[k]=1ll*f[k]*s%P*f[edge[i].to]%P;
}
}
bool check(int i){edge[i].op++;if (i&1) edge[i+1].op++;else edge[i-1].op++;return edge[i].op<=1;}
bool maketag(int x,int y,int i)
{
if (!check(i)) return 0;
while (x!=y) {if (!check(from[x])) return 0;x=fa[x];}
return 1;
}
bool iscactus(int k)
{
flag[k]=1;
for (int i=p[k];i;i=edge[i].nxt)
if (edge[i].to!=fa[k])
if (flag[edge[i].to]) {if (deep[edge[i].to]<deep[k]&&!maketag(k,edge[i].to,i)) return 0;}
else
{
fa[edge[i].to]=k;
deep[edge[i].to]=deep[k]+1;
from[edge[i].to]=i;
if (!iscactus(edge[i].to)) return 0;
}
return 1;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4784.in","r",stdin);
freopen("bzoj4784.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
T=read();
while (T--)
{
n=read(),m=read();
t=0;for (int i=1;i<=n;i++) p[i]=0,size[i]=0,f[i]=1,flag[i]=0,deep[i]=0;
fac[0]=1;for (int i=1;i<=n;i++) fac[i]=1ll*fac[i-1]*i%P;
inv[0]=inv[1]=1;for (int i=2;i<=n;i++) inv[i]=P-1ll*(P/i)*inv[P%i]%P;
inv2[0]=1;for (int i=1;i<=n;i++) inv2[i]=1ll*inv2[i-1]*inv[2]%P;
for (int i=2;i<=n;i++) inv[i]=1ll*inv[i]*inv[i-1]%P;
for (int i=1;i<=m;i++)
{
int x=read(),y=read();
addedge(x,y),addedge(y,x);
}
if (!iscactus(1)) {printf("0\n");continue;}
for (int i=1;i<=n;i++) flag[i]=0;
int ans=1;
for (int k=1;k<=n;k++)
if (!flag[k])
{
dfs(k);
int s=0;
for (int i=0;i<=size[k]/2;i++) inc(s,calc(size[k],i));
ans=1ll*ans*s%P*f[k]%P;
}
printf("%d\n",ans);
}
return 0;
}
BFS
在BFS图（无向图）中 。边只可能在相邻的两层或同一层之间连（BFS最优解的特性），并且每个点至少和上一层的一个点相连(按照距离分层)
强连通/双连通分量（$$Tarjan$$）
远古套路0：
强连通缩点，在DAG上DP
//缩点
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
struct Edge
{
int from;
int to;
int next;
}e[200005],E[200005];
int n,m,edgenum,head[10005],w[10005],W[10005],low[10005],dfn[10005],where[10005];
int scc,stack[10005],f[10005],in[10005],top,ans;
queue<int>q;
vector<int>SCC[10005];
bool flag[10005];
void add(int u,int v)
{
e[++edgenum].to=v;
e[edgenum].from=u;
e[edgenum].next=head[u];
head[u]=edgenum;
}
int ind=0;
void Tarjan(int node,int fa)
{
if(dfn[node])return;
dfn[node]=++ind;
low[node]=dfn[node];
stack[++top]=node;
flag[node]=1;
for(int hd=head[node];hd;hd=e[hd].next)
{
if(!dfn[e[hd].to])
{
Tarjan(e[hd].to,node);
low[node]=min(low[node],low[e[hd].to]);
}
else if(flag[e[hd].to])
{
low[node]=min(low[node],dfn[e[hd].to]);
}
}
if(low[node]==dfn[node])
{
int v=stack[top--];
SCC[++scc].push_back(v);
where[v]=scc;
flag[v]=0;
W[scc]+=w[v];
while(v!=node)
{
v=stack[top--];
SCC[scc].push_back(v);
where[v]=scc;
flag[v]=0;
W[scc]+=w[v];
}
}
}
void add2(int hd)
{
E[++edgenum].from=where[e[hd].from];
E[edgenum].to=where[e[hd].to];
E[edgenum].next=head[E[edgenum].from];
head[E[edgenum].from]=edgenum;
in[E[edgenum].to]++;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&w[i]);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
Tarjan(i,-1);
edgenum=0;
memset(head,0,sizeof(head));
for(int i=1;i<=m;i++)
{
if(where[e[i].from]!=where[e[i].to])
add2(i);
}
for(int i=1;i<=scc;i++)
if(in[i]==0)
{
q.push(i);
f[i]=W[i];
ans=max(ans,f[i]);
}
while(!q.empty())
{
int node=q.front();
q.pop();
ans=max(ans,f[node]);
for(int hd=head[node];hd;hd=E[hd].next)
{
f[E[hd].to]=max(f[E[hd].to],f[node]+W[E[hd].to]);
in[E[hd].to]--;
if(in[E[hd].to]==0)
{
q.push(E[hd].to);
}
}
}
printf("%d\n",ans);
return 0;
}
套路1：
边（点）双联通分量缩起来形成一棵树，然后在树上搞事情。（比如加最少边让这个图变成双连通）
若一个无向连通图不存在割点，则称它为“点双连通图”。若一个无向连通图不存在割边，则称它为“边双连通图”。
无向图的极大点双连通子图称为“点双连通分量”，简记为“v-DCC”。无向连通图的极大边双连通子图被称为“边双连通分量”，简记为“e-DCC”。二者统称为“双连通分量”，简记为“DCC”。
点双连通分量处理起来比较麻烦
例题：加最少边让图变成双连通（做法：先缩边双联通分量，然后答案就是$$ \lceil 叶子节点/2 \rceil $$
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define lson x<<1
#define rson x<<1|1
#define ll long long
#define rint register int
#define mid ((st[x].l + st[x].r) >> 1)
using namespace std;
template <typename xxx> inline void read(xxx &x) {
char c = getchar(),f = 1;x = 0;
for(;c ^ '-' && !isdigit(c);c = getchar());
if(c == '-') c = getchar(),f = -1;
for(;isdigit(c);c = getchar()) x = (x<<1) + (x<<3) + (c ^ '0');
x *= f;
}
template<typename xxx> inline void print(xxx x)
{
if(x<0){putchar('-');x=-x;}
if(x>9) print(x/10);
putchar(x%10+'0');
}
const int maxn = 200010;
const int inf = 0x7fffffff;
const int mod = 1e9 + 7;
struct edge{
int to,last,fg,from;
}e[maxn];
int head[maxn],tot;
inline void add(int from,int to) {
++tot;
e[tot].to = to;
e[tot].from = from;
e[tot].last = head[from];
head[from] = tot;
}
int n,m;
int dfn[maxn],low[maxn],cnt;
inline void tarjan(int x,int in_edge) {
dfn[x] = low[x] = ++cnt;
for(rint i = head[x];i; i = e[i].last) {
if(!dfn[e[i].to]) {
tarjan(e[i].to,i);
if(low[e[i].to] < low[x]) low[x] = low[e[i].to];
if(low[e[i].to] > dfn[x]) {
e[i].fg = e[i^1].fg = 1;
}
}
else if(i ^ (in_edge ^ 1) && dfn[e[i].to] < low[x]) low[x] = dfn[e[i].to];
}
}
int col[maxn],num,in[maxn];
inline void ddfs(int x) {
col[x] = num;
for(rint i = head[x];i;i = e[i].last) {
if(col[e[i].to] || e[i].fg) continue;
ddfs(e[i].to);
}
}
int main()
{
read(n);read(m);tot = 1;
for(rint i = 1;i <= m; ++i) {
int x,y;
read(x);read(y);
add(x,y);add(y,x);
}
for(rint i = 1;i <= n; ++i) {
if(!dfn[i]) {
tarjan(i,0);
}
}
for(rint i = 1;i <= n; ++i) {
if(!col[i]) {
++num;
ddfs(i);
}
}
for(rint i = 2;i <= tot; ++i) {
if(col[e[i].from] == col[e[i].to]) continue;
++in[col[e[i].from]];
++in[col[e[i].to]];
}
int ans = 0;
for(rint i = 1;i <= num; ++i)
if(in[i] == 2) ++ans;
print((ans + 1) / 2);
return 0;
}
套路2：
动态维护边双连通分量树
（离线：先建树后处理。在线：$$lct$$/虚树）
//BZOJ2959 长跑
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<bitset>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define pr pair<int,int>
#define ll long long
using namespace std;
int g[150010];
int fa[150010];
int f[150010];
int s[150010][2];
int v[150010];
int sum[150010];
int size[150010];
int st[150010];
int r[150010];
int n,m;
int opt;
int x,y;
int find(int x)
{
if(fa[x]==x)
{
return x;
}
return fa[x]=find(fa[x]);
}
int judge(int x)
{
if(g[x]==x)
{
return x;
}
return g[x]=judge(g[x]);
}
int is_root(int rt)
{
return rt!=s[find(f[rt])][0]&&rt!=s[find(f[rt])][1];
}
int get(int rt)
{
return rt==s[find(f[rt])][1];
}
void pushup(int rt)
{
sum[rt]=sum[s[rt][0]]+sum[s[rt][1]]+size[rt];
}
void pushdown(int rt)
{
if(r[rt])
{
swap(s[rt][0],s[rt][1]);
r[s[rt][0]]^=1;
r[s[rt][1]]^=1;
r[rt]^=1;
}
}
void rotate(int rt)
{
int fa=find(f[rt]);
int anc=find(f[fa]);
int k=get(rt);
if(!is_root(fa))
{
s[anc][get(fa)]=rt;
}
s[fa][k]=s[rt][k^1];
f[s[fa][k]]=fa;
s[rt][k^1]=fa;
f[fa]=rt;
f[rt]=anc;
pushup(fa);
pushup(rt);
}
void splay(int rt)
{
int top=0;
st[++top]=rt;
for(int i=rt;!is_root(i);i=find(f[i]))
{
st[++top]=find(f[i]);
}
for(int i=top;i>=1;i--)
{
pushdown(st[i]);
}
for(int fa;!is_root(rt);rotate(rt))
{
if(!is_root(fa=find(f[rt])))
{
rotate(get(fa)==get(rt)?fa:rt);
}
}
}
void access(int rt)
{
for(int x=0;rt;x=rt,rt=find(f[rt]))
{
splay(rt);
s[rt][1]=x;
pushup(rt);
}
}
void reverse(int rt)
{
access(rt);
splay(rt);
r[rt]^=1;
}
void link(int x,int y)
{
reverse(x);
f[x]=y;
}
void dfs(int x,int rt)
{
fa[x]=rt;
if(s[x][0])
{
dfs(s[x][0],rt);
}
if(s[x][1])
{
dfs(s[x][1],rt);
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&v[i]);
size[i]=v[i];
sum[i]=v[i];
fa[i]=i;
g[i]=i;
}
while(m--)
{
scanf("%d%d%d",&opt,&x,&y);
int fx=find(x);
int fy=find(y);
if(opt==1)
{
if(fx!=fy)
{
if(judge(fx)!=judge(fy))
{
link(fx,fy);
g[g[fx]]=g[fy];
}
else
{
reverse(fx);
access(fy);
splay(fy);
size[fy]=sum[fy];
dfs(fy,fy);
s[fy][0]=0;
}
}
}
else if(opt==2)
{
splay(fx);
size[fx]+=y-v[x];
sum[fx]+=y-v[x];
v[x]=y;
}
else
{
if(judge(fx)!=judge(fy))
{
printf("-1\n");
}
else
{
reverse(fx);
access(fy);
splay(fy);
printf("%d\n",sum[fy]);
}
}
}
}
在OI比赛中结合数据结构考（图论模型一般比较明显）。
//强连通分量
#include<queue>
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
vector<int> g[10010];
int color[10010],dfn[20020],low[20020],stack[20020],vis[10010],cnt[10010];
int deep,top,n,m,sum,ans;
void tarjan(int u)
{
dfn[u]=++deep;
low[u]=deep;
vis[u]=1;
stack[++top]=u;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
int v=g[u][i];
if(!dfn[v])
{
tarjan(v);
low[u]=min(low[u],low[v]);
}
else
{
if(vis[v])
{
low[u]=min(low[u],low[v]);
}
}
}
if(dfn[u]==low[u])
{
color[u]=++sum;
vis[u]=0;
while(stack[top]!=u)
{
color[stack[top]]=sum;
vis[stack[top--]]=0;
}
top--;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
tarjan(i);
}
}
for(int i=1;i<=n;i++)
{
cnt[color[i]]++;
}
for(int i=1;i<=sum;i++)
{
if(cnt[i]>1)
{
ans++;
}
}
printf("%d\n",ans);
}
//割点
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define hi printf("hi!");
using namespace std;
vector<int> g[10010];
int dfn[10010],low[10010],iscut[10010],son[10010];
int deep,root,n,m,ans;
int tarjan(int u,int fa)
{
int child=0,lowu;
lowu=dfn[u]=++deep;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
int v=g[u][i];
if(!dfn[v])
{
child++;
int lowv=tarjan(v,u);
lowu=min(lowu,lowv);
if(lowv>dfn[u])
{
iscut[u]=1;
}
}
else
{
if(v!=fa&&dfn[v]<dfn[u])
{
lowu=min(lowu,dfn[v]);
}
}
}
if(fa<0&&child==1)
{
iscut[u]=false;
}
low[u]=lowu;
return lowu;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
root=i;
tarjan(i,-1);
}
}
for(int i=1;i<=n;i++)
{
if(iscut[i])
{
ans++;
}
}
printf("%d\n",ans);
for(int i=1;i<=n;i++)
{
if(iscut[i])
{
printf("%d ",i);
}
}
}
//割边/桥
#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#define hi printf("hi!");
using namespace std;
vector<pair<int,int> >bridge;
vector<int> g[10010];
int dfn[10010],low[10010];
int deep,root,n,m,ans;
int tarjan(int u,int fa)
{
int lowu;
lowu=dfn[u]=++deep;
int sz=g[u].size();
for(int i=0;i<sz;i++)
{
int v=g[u][i];
if(!dfn[v])
{
int lowv=tarjan(v,u);
lowu=min(lowu,lowv);
if(lowv>dfn[u])
{
int from,to;
from=u;
to=v;
if(from>to)
{
swap(from,to);
}
bridge.push_back(make_pair(from,to));
}
}
else
{
if(v!=fa&&dfn[v]<dfn[u])
{
lowu=min(lowu,dfn[v]);
}
}
}
low[u]=lowu;
return lowu;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int from,to;
scanf("%d%d",&from,&to);
g[from].push_back(to);
g[to].push_back(from);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
{
root=i;
tarjan(i,-1);
}
}
for(int i=0;i<bridge.size();i++)
{
printf("%d %d\n",bridge[i].first,bridge[i].second);
}
}
欧拉回路（它很妙）
需要掌握正确的有/无向图的欧拉回路/路径的求法
#include "bits/stdc++.h"
using namespace std;
const int maxn = 1e3;
int vis[maxn][maxn];
int n, m, x, y;
vector<int> e[maxn];
deque<int> q;
void addEdge(int a, int b) {
e[a].push_back(b);
e[b].push_back(a);
}
bool dfs(int now, int sum) {
if (sum == m) {
while (!q.empty()) {
cout << q.back() << " ";
q.pop_back();
}
cout << endl;
return 1;
}
for (int i = 0; i < e[now].size(); i++) {
if (!vis[now][e[now][i]]) {
vis[now][e[now][i]] = 1;
vis[e[now][i]][now] = 1;
q.push_front(e[now][i]);
if (dfs(e[now][i], sum + 1))
return 1;
q.pop_front();
vis[now][e[now][i]] = 0;
vis[e[now][i]][now] = 0;
}
}
return 0;
}
int main() {、
cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> x >> y;
addEdge(x, y);
}
q.push_front(1);
if (!dfs(1, 0))
cout << "NO answer" << endl;
return 0;
}
套路1：
构造（构造一个序列或者能得一个无向图定向使得入度和出度差不超过1）
平面上有n个点$$(x,y)$$，将这些点红蓝染色实点每行每列的红蓝点个数的差不超过1（解法x,y建边，然后定向，染色真TM奇特）。
生成$$2^n$$ 的01串（串首尾相连），使得所有长度为n的01串都出现过
套路2：
根据充要条件处理度数（有向图联通其入度=出度；无向图只要联通且度数是偶数）
无向图加最少的边使得整个图成为欧拉图（做法为原理）。
混合图欧拉回路（无向图定向，性质）
//POJ 1637
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
const int MAXN = 1010;
const int MAXM = 50010;
const int INF = 0x3f3f3f3f;
struct Edge
{
int v, f;
int next;
}edge[MAXM];
int n, m;
int cnt;
int s, t;
int first[MAXN], level[MAXN];
int q[MAXN];
int ind[MAXN], outd[MAXN];
int totFlow;
void init()
{
cnt = 0;
totFlow = 0;
memset(first, -1, sizeof(first));
memset(ind, 0, sizeof(ind));
memset(outd, 0, sizeof(outd));
}
void read(int u, int v, int f)
{
edge[cnt].v = v, edge[cnt].f = f;
edge[cnt].next = first[u], first[u] = cnt++;
}
void read_graph(int u, int v, int f)
{
read(u, v, f);
read(v, u, 0);
}
int bfs(int s, int t)
{
memset(level, 0, sizeof(level));
level[s] = 1;
int front = 0, rear = 1;
q[front] = s;
while(front < rear)
{
int x = q[front++];
if(x == t) return 1;
for(int e = first[x]; e != -1; e = edge[e].next)
{
int v = edge[e].v, f = edge[e].f;
if(!level[v] && f)
{
level[v] = level[x] + 1;
q[rear++] = v;
}
}
}
return 0;
}
int dfs(int u, int maxf, int t)
{
if(u == t) return maxf;
int ret = 0;
for(int e = first[u]; e != -1; e = edge[e].next)
{
int v = edge[e].v, f = edge[e].f;
if(level[v] == level[u] + 1 && f)
{
int Min = min(maxf-ret, f);
f = dfs(v, Min, t);
edge[e].f -= f;
edge[e^1].f += f;
ret += f;
if(ret == maxf) return ret;
}
}
return ret;
}
int Dinic(int s, int t)
{
int ans = 0;
while(bfs(s, t)) ans += dfs(s, INF, t);
return ans;
}
void read_case()
{
init();
scanf("%d%d", &n, &m);
while(m--)
{
int u, v, flag;
scanf("%d%d%d", &u, &v, &flag);
outd[u]++, ind[v]++;
if(u != v)
{
if(!flag) read_graph(u, v, 1);
}
}
}
int build()
{
int flag = 1;
s = 0, t = n+1;
for(int i = 1; i <= n; i++)
{
if((ind[i]+outd[i]) & 1) //出度加入度是奇数
{
return 0;
}
else if(outd[i] > ind[i]) //出度大于入度
{
int dif = outd[i]-ind[i];
read_graph(s, i, dif/2);
totFlow += dif/2;
} //可能有入度等于出度的情况,连不连无所谓
else
{
int dif = ind[i]-outd[i];
read_graph(i, t, dif/2);
}
}
return 1;
}
void solve()
{
read_case();
int flag = build();
int ans = Dinic(s, t);
if(!flag) printf("impossible\n");
else if(ans >= totFlow) printf("possible\n");
else printf("impossible\n");
}
int main()
{
int T;
scanf("%d", &T);
while(T--)
{
solve();
}
return 0;
}
2-SAT
（掌握做法和输出方案）
//2-sat
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct Edge
{
int from;
int to;
int next;
}e[4000005];
int n,m,edgenum,head[2000005],p[2000005];
int dfn[2000005],low[2000005],st[2000005],scc,top;
bool flag[2000005];
queue<int>q;
void add(int u,int v)
{
e[++edgenum].from=u;
e[edgenum].to=v;
e[edgenum].next=head[u];
head[u]=edgenum;
}
int ind;
void Tarjan(int node)
{
st[++top]=node;
dfn[node]=low[node]=++ind;
flag[node]=1;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(!dfn[to])
{
Tarjan(to);
low[node]=min(low[node],low[to]);
}
else if(flag[to])low[node]=min(low[node],dfn[to]);
}
if(low[node]==dfn[node])
{
int v=st[top--];
scc++;
flag[v]=0;
p[v]=scc;
while(v!=node)
{
v=st[top--];
flag[v]=0;
p[v]=scc;
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int x1,v1,x2,v2;
scanf("%d%d%d%d",&x1,&v1,&x2,&v2);
add(x1+(!v1)*n,x2+v2*n);
add(x2+(!v2)*n,x1+v1*n);
}
for(int i=1;i<=2*n;i++)
if(!dfn[i])Tarjan(i);
for(int i=1;i<=n;i++)
{
if(p[i]==p[n+i])
{
printf("IMPOSSIBLE\n");
return 0;
}
}
printf("POSSIBLE\n");
int num=edgenum;
edgenum=0;
memset(head,0,sizeof(head));
memset(low,0,sizeof(low));
for(int i=1;i<=edgenum;i++)
{
int u=e[i].from,v=e[i].to;
if(p[u]!=p[v])
{
add(p[u],p[v]);
low[p[v]]++;
}
}
ind=0;
for(int i=1;i<=scc;i++)
if(low[i]==0)
q.push(i);
while(!q.empty())
{
int node=q.front();
q.pop();
dfn[node]=++ind;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
low[to]--;
if(low[to]==0)q.push(to);
}
}
for(int i=1;i<=n;i++)
{
if(dfn[p[i]]>dfn[p[i+n]])putchar('1');
else putchar('0');
putchar(' ');
}
putchar('\n');
return 0;
}
套路 1：
建立辅助变量优化建图
会结合一些数据结构的常见手段（线段树 ST表 前缀 后缀）
比如一些变量至多只有一个可以为1的建图方法（不会）
套路2：
对于变量取值，拆除一堆$$x\leqslant1,x\leqslant2,x\leqslant3,……, $$这样的变量记作$$p_1,p_2,p_3,……$$
然后连$$p_2 \to p_1,p_1^, \to p_2^,,…… $$这样保证前面的取的是1，后面的取的是0
然后再根据不等式之类的限制连边。
套路3：
额外加一个限制，判断可不可行之类的。
相当于在这个图中加了两条边，判断$$x与x^,$$可不可达，转化到可达性问题。
Dominator Tree（支配树）
会吗并不会，考吗并不考。
//luogu-P5180
# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# define sz 20
# define FOR(i,st,ed) for(int i=st;i<=ed;++i)
# define _FOR(tu,u) for(int v,i=tu.hd[u];i;i=tu.e[i].nt)
# define _(tu) v=tu.e[i].to;
using namespace std;
int re(){
int s=0,f=1;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
while(isdigit(ch)){s=(s<<1)+(s<<3)+ch-'0';ch=getchar();}
return s*f;
}//快读就不解释了
const int N=2e5+7;
struct MAP{
struct edge{
int to,nt;
}e[N<<1];int cnt,hd[N];
void link(int x,int y){e[++cnt]=(edge){y,hd[x]};hd[x]=cnt;}
}xx,a,ra,t,rt,z;//排除xx，依次表示原图，原图的反图，dfs树
//dfs树的反图，和最后的支配树
int n,m;
int dfn[N],dji,id[N],ff[N];//ff表示dfs树上的父节点
void dfs(int u){
id[dfn[u]=++dji]=u;
_FOR(a,u){
_(a);
if(!dfn[v]) dfs(v),ff[v]=u,t.link(u,v);
}
}//扣出一个dfs树
int anc[N],semi[N],mn[N];//这个mn[v],表示v点的dfs树上的祖先
//的semi最小的那个祖先，所以semi[mn[x]]=semi[x];
void init(){
FOR(i,1,n) anc[i]=semi[i]=mn[i]=i;
}
int find(int u){
if(u!=anc[u]){
int t=anc[u];anc[u]=find(anc[u]);
if(dfn[semi[mn[u]]]>dfn[semi[mn[t]]]) mn[u]=mn[t];
}
return anc[u];
}//以上是带权并查集(路径压缩)
void len_tarjan(){
init();
for(int j=n;j>=2;--j){
int u=id[j],res=j;
if(!u) continue;
_FOR(ra,u){
_(ra);
if(!dfn[v]) continue;
if(dfn[v]<dfn[u]) res=min(res,dfn[v]);
else find(v),res=min(res,dfn[semi[mn[v]]]);
}
semi[u]=id[res];anc[u]=ff[u];t.link(semi[u],u);
}
}//我们的tarjan大佬的算法
int ru[N],dep[N],fa[N][25];
int lca(int x,int y){
if(dep[x]<dep[y]) swap(x,y);
int del=dep[x]-dep[y];
FOR(i,0,sz)
if((1<<i)&del) x=fa[x][i];
if(x==y) return x;
for(int i=sz;i>=0;--i)
if(fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}/lca
void work(int u){
int t=rt.e[rt.hd[u]].to;
_FOR(rt,u){
_(rt);t=lca(t,v);
}
dep[u]=dep[t]+1;
fa[u][0]=t;
z.link(t,u);
FOR(i,1,sz)
fa[u][i]=fa[fa[u][i-1]][i-1];
}//建立支配树
void tpsort(){
FOR(j,1,n)
_FOR(t,j){
_(t);
ru[v]++;rt.link(v,j);
}
FOR(i,1,n) if(!ru[i]) t.link(0,i),rt.link(i,0);
queue <int> q;q.push(0);
while(q.size()){
int u=q.front();q.pop();
_FOR(t,u){
_(t);
if((--ru[v])<=0) q.push(v),work(v);
}
}
}
int siz[N];
void adfs(int u){
siz[u]=1;
_FOR(z,u){
_(z);adfs(v);siz[u]+=siz[v];
}
}//最后adfs用来搜答案
int main(){
n=re();m=re();int x,y;
FOR(i,1,m){
x=re();y=re();
a.link(x,y);ra.link(y,x);
}
dfs(1);
len_tarjan();
tpsort();
adfs(0);
FOR(i,1,n) cout<<siz[i]<<' ';
return 0;
}
最短路
套路：
割点/边问最短路：
删边最短路一般来说都是考虑最短路径树，然后考虑每条非树边当成替换边之类的。
删点可以使用分治解决。
（$$dijkstra$$）边权小的话可以把堆换成桶解决。
变种:
比如边权，距离，价格有关之类的，可以用$$dijkstr$$每次确定最小值解决。
还有一些题的某些参数不知道，告诉你某些点之间的最短路的范围，然后求边权或者之类的
有些题目是可以通过一些精妙的分析解决。（一般可以写成线性规划，之间使用$$simplex$$ $$overkill$$一下就行了）
//dijkstra
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
struct Edge
{
int to;
int nxt;
int len;
}e[200005];
int n,m,s,edgenum,head[100005],dis[100005];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
void add(int u,int v,int l)
{
e[++edgenum].len=l;
e[edgenum].to=v;
e[edgenum].nxt=head[u];
head[u]=edgenum;
}
void Dijkstra()
{
memset(dis,0x7f,sizeof(dis));
dis[s]=0;
q.push(make_pair(0,s));
while(!q.empty())
{
int d=q.top().first;
int node=q.top().second;
q.pop();
if(dis[node]!=d)continue;
for(int hd=head[node];hd;hd=e[hd].nxt)
{
int to=e[hd].to;
if(dis[to]>dis[node]+e[hd].len)
{
dis[to]=dis[node]+e[hd].len;
q.push(make_pair(dis[to],to));
}
}
}
}
int main()
{
scanf("%d%d%d",&n,&m,&s);
for(int i=1;i<=m;i++)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
add(u,v,l);
}
Dijkstra();
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
printf("\n");
return 0;
}
//SPFA
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct Edge
{
int to;
int len;
int next;
}e[100005];
int n,m,edgenum,head[10005],dis[10005],num[10005];
bool flag[10005];
queue<int>q;
void add(int u,int v,int l)
{
e[++edgenum].len=l;
e[edgenum].to=v;
e[edgenum].next=head[u];
head[u]=edgenum;
}
bool SPFA(int i)
{
memset(dis,0x7f,sizeof(dis));
dis[i]=0;
q.push(i);
flag[i]=1;
while(!q.empty())
{
int node=q.front();
q.pop();
flag[node]=0;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(dis[to]>dis[node]+e[hd].len)
{
dis[to]=dis[node]+e[hd].len;
if(!flag[to])
{
q.push(to);
flag[to]=1;
num[to]++;
if(num[to]>m)return 0;
}
}
}
}
return 1;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v,l;
scanf("%d%d%d",&u,&v,&l);
add(u,v,l);
}
if(!SPFA(1))
{
printf("No solution\n");
return 0;
}
for(int i=1;i<=n;i++)
printf("%d ",dis[i]);
printf("\n");
return 0;
}
K短路
求k优解，或者之间问k短路。
做法：A*或者可并堆（反正都不会）。
//A*
#include <bits/stdc++.h>
using namespace std;
typedef double db;
db dis[5005],f[5005];
int t[5005],vis[5005];
struct dat
{
int u;
db w;
bool operator < (const dat &rhs) const {
return w>rhs.w;
}
};
vector<dat> G[5005],g[5005];
void addedge(int i,int j,db w)
{
G[i].push_back((dat){j,w});
g[j].push_back((dat){i,w});
}
signed main()
{
int n,m,ans=0;
db e;
cin>>n>>m>>e;
for (int i=1;i<=m;i++)
{
int u,v;
db w;
cin>>u>>v>>w;
addedge(u,v,w);
}
memset(f,127,sizeof(f));
f[n]=0;
priority_queue<dat> q,Q;
Q.push((dat){n,0});
while (!Q.empty())
{
dat p=Q.top();Q.pop();
int u=p.u;
if (vis[u]) continue;
vis[u]=1;
for (int i=0;i<g[u].size();i++)
{
dat v=g[u][i];
if (f[u]+v.w<f[v.u])
{
Q.push((dat){v.u,f[u]+v.w});
f[v.u]=f[u]+v.w;
}
}
}
q.push((dat){1,f[1]});
while (!q.empty())
{
dat p=q.top();q.pop();
int u=p.u;
db w=p.w-f[u];
if (u==n)
{
e-=w;
if (e>=1e-6) ans++;
else break;
continue;
}
for (int i=0;i<G[u].size();i++)
{
dat v=G[u][i];
q.push((dat){v.u,w+v.w+f[v.u]});
}
}
cout<<ans<<endl;
return 0;
}
//可并堆
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class Num> inline void Cmax(Num &x, const Num y) {
x = y > x ? y : x;
}
template <class Num> inline void Cmin(Num &x, const Num y) {
x = y < x ? y : x;
}
const int maxn(5005);
const int maxm(2e5 + 5);
const double eps(1e-8);
int n, m, first[maxn], cnt, vis[maxn], rt[maxn], tot, cov[maxm << 1], ans, fa[maxn];
double se, e, dis[maxn];
priority_queue < pair <double, int> > q;
struct Heap {
int ls, rs, dis, ed;
double w;
} tr[maxm * 20];
struct Edge {
int to, next;
double w;
} edge[maxm << 1];
inline void Add(int u, int v, double w) {
edge[cnt] = (Edge){v, first[u], w}, first[u] = cnt++;
edge[cnt] = (Edge){u, first[v], w}, first[v] = cnt++;
}
inline int NewNode(double w, int ed) {
int x = ++tot;
tr[x].w = w, tr[x].dis = 1, tr[x].ed = ed;
return x;
}
int Merge(int x, int y) {
if (!x || !y) return x + y;
if (tr[x].w - tr[y].w >= eps) swap(x, y);
int p = ++tot;
tr[p] = tr[x], tr[p].rs = Merge(tr[p].rs, y);
if (tr[tr[p].ls].dis < tr[tr[p].rs].dis) swap(tr[p].ls, tr[p].rs);
tr[p].dis = tr[tr[x].rs].dis + 1;
return p;
}
void Dfs(int u) {
vis[u] = 1;
for (int e = first[u], v; e != -1; e = edge[e].next)
if (e & 1) {
double w = edge[e].w;
if (fabs(dis[u] + w - dis[v = edge[e].to]) < eps && !vis[v])
fa[v] = u, cov[e ^ 1] = 1, Dfs(v);
}
}
int main() {
memset(first, -1, sizeof(first));
memset(dis, 127, sizeof(dis));
scanf("%d%d%lf", &n, &m, &se);
for (int i = 1, u, v; i <= m; ++i) scanf("%d%d%lf", &u, &v, &e), Add(u, v, e);
dis[n] = 0, q.push(make_pair(0, n));
while (!q.empty()) {
int u = q.top().second;
q.pop();
if (vis[u]) continue;
vis[u] = 1;
for (int e = first[u]; ~e; e = edge[e].next)
if (e & 1) {
int v = edge[e].to;
if (dis[v] - (dis[u] + edge[e].w) >= eps)
q.push(make_pair(-(dis[v] = dis[u] + edge[e].w), v));
}
}
for (int i = 1; i <= n; ++i) vis[i] = 0;
Dfs(n);
for (int e = 0, u, v; e < cnt; e += 2)
if (!cov[e]) {
u = edge[e ^ 1].to, v = edge[e].to;
if (dis[u] == dis[0] || dis[v] == dis[0]) continue;
rt[u] = Merge(rt[u], NewNode(dis[v] + edge[e].w - dis[u], v));
}
for (int i = 1; i <= n; ++i) q.push(make_pair(-dis[i], i));
for (int i = 1, u; i <= n; ++i) {
u = q.top().second, q.pop();
if (fa[u]) rt[u] = Merge(rt[u], rt[fa[u]]);
}
if (dis[1] - se < eps) se -= dis[1], ++ans;
if (rt[1]) q.push(make_pair(-tr[rt[1]].w, rt[1]));
while (!q.empty()) {
int ed = q.top().second;
double cur = q.top().first, w = dis[1] - cur;
if (w - se >= eps) break;
q.pop(), se -= w, ++ans;
for (int i = 0; i < 2; ++i) {
int nxt = i ? tr[ed].rs : tr[ed].ls;
if (nxt) q.push(make_pair(cur + tr[ed].w - tr[nxt].w, nxt));
}
if (rt[tr[ed].ed]) q.push(make_pair(cur - tr[rt[tr[ed].ed]].w, rt[tr[ed].ed]));
}
printf("%d\n", ans);
return 0;
}
差分约束
对于$$s(v)\leqslant s(u)+w(u,v)$$的限制建图，然后求解。
一般就是根据题意把变量和限制写出来，如果每个限制都只和某两项的差有关，可以使用差分约束解决。
考虑前缀和也是常见手段。
//luogu-p1993
#include<bits/stdc++.h>
#define il inline
#define For(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
using namespace std;
const int N=50005,inf=23333333;
int n,m,to[N],net[N],w[N],dis[N],cnt,h[N],tot[N];
bool vis[N];
il int gi(){
int a=0;char x=getchar();
while(x<'0'||x>'9')x=getchar();
while(x>='0'&&x<='9')a=(a<<3)+(a<<1)+x-48,x=getchar();
return a;
}
il void add(int u,int v,int c){to[++cnt]=v,net[cnt]=h[u],h[u]=cnt,w[cnt]=c;}
il bool spfa(int u){
vis[u]=1;
for(int i=h[u];i;i=net[i])
if(dis[to[i]]<dis[u]+w[i]){
dis[to[i]]=dis[u]+w[i];
if(vis[to[i]])return 0;
if(!spfa(to[i]))return 0;
}
vis[u]=0;
return 1;
}
int main(){
n=gi(),m=gi();
int f,a,b,c;
while(m--){
f=gi(),a=gi(),b=gi();
if(f==1)c=gi(),add(b,a,c);
else if(f==2)c=gi(),add(a,b,-c);
else if(f==3)add(a,b,0),add(b,a,0);
}
For(i,1,n)add(0,i,0),dis[i]=-inf;
if(!spfa(0))cout<<"No";
else cout<<"Yes";
return 0;
}
网络流
最好能掌握多种费用流算法（$$SPFA$$增广，$$dkw$$费用流），以及掌握有负环/上下界的费用流。最大流（$$dinic$$）；
//spfa增广
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=705,maxe=144005,INF=0x3f3f3f3f;
int N,M,S,T,n,tim[65][15],id[65][15],ans=0;
int tot=1,son[maxe],nxt[maxe],lnk[maxn],flw[maxe],cap[maxe],w[maxe];
void add(int x,int y,int z){
son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;flw[tot]=0;cap[tot]=1;w[tot]=z;
son[++tot]=x;nxt[tot]=lnk[y];lnk[y]=tot;flw[tot]=0;cap[tot]=0;w[tot]=-z;
}
#define nc getchar
inline int red(){
int tot=0,f=1;char ch=nc();
while (ch<'0'||'9'<ch) {if (ch=='-') f=-f;ch=nc();}
while ('0'<=ch&&ch<='9') tot=tot*10+ch-48,ch=nc();
return tot*f;
}
int que[maxn],dst[maxn],fa[maxn],ed[maxn];
bool vis[maxn];
bool spfa(){
memset(dst,63,sizeof(dst));
memset(vis,0,sizeof(vis));
int hed=0,til=1;
que[1]=S;dst[S]=0;fa[S]=0;
while (hed!=til){
int x=que[hed=(hed+1)%maxn];
vis[x]=0;
for (int j=lnk[x];j;j=nxt[j])
if (cap[j]>flw[j]&&dst[son[j]]>dst[x]+w[j]){
dst[son[j]]=dst[x]+w[j];
fa[son[j]]=x;ed[son[j]]=j;
if (!vis[son[j]])
vis[son[j]]=1,
que[til=(til+1)%maxn]=son[j];
}
}
if (dst[T]==INF) return 0;
return 1;
}
int main(){
//do something...
while (spfa()){
int Min=INF;
for (int j=T;j!=S;j=fa[j]) Min=min(Min,cap[ed[j]]-flw[ed[j]]);
for (int j=T;j!=S;j=fa[j]) flw[ed[j]]+=Min,flw[ed[j]^1]-=Min;
ans+=dst[T]*Min;
}
printf("%.2lf",(double)ans/N);
return 0;
}
//dinic
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
const int INF=2147483647;
struct Edge
{
int from;
int to;
int next;
int flow;
}e[200005];
int n,m,s,t,edgenum=1,dep[50005],head[50005];
queue<int>q;
void add(int u,int v,int f)
{
e[++edgenum].flow=f;
e[edgenum].from=u;
e[edgenum].to=v;
e[edgenum].next=head[u];
head[u]=edgenum;
}
bool bfs()
{
while(!q.empty())q.pop();
memset(dep,0,sizeof(dep));
dep[s]=1;
q.push(s);
while(!q.empty())
{
int node=q.front();
q.pop();
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(e[hd].flow&&dep[to]==0)
{
dep[to]=dep[node]+1;
q.push(to);
}
}
}
return dep[t];
}
int dfs(int node,int nowf)
{
if(node==t)return nowf;
for(int hd=head[node];hd;hd=e[hd].next)
{
int to=e[hd].to;
if(dep[to]==dep[node]+1&&e[hd].flow)
{
int d=dfs(to,min(nowf,e[hd].flow));
if(d>0)
{
e[hd].flow-=d;
e[hd^1].flow+=d;
return d;
}
}
}
return 0;
}
int Dinic()
{
int ans=0,d;
while(bfs())
{
while(d=dfs(s,INF))
ans+=d;
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
int u,v,f;
scanf("%d%d%d",&u,&v,&f);
add(u,v,f);
add(v,u,0);
}
printf("%d\n",Dinic());
return 0;
}
套路0：
有负环/上下界的最大/最小/费用/循环流（无源点和汇点）。
套路1：
建立线性规划的式子然后对偶成为费用流。($$ simplex $$不会比对偶费用流慢多少，之间背有初始解的模板）
套路2：
建立一堆辅助变量变成等式，然后通过一些高明的技巧使得每个东西一正一反出现在这些等式里，然后根据流量平衡见图。
一般来说这些$$LP-based$$的网络流题都是费用流。因为最大流的对偶是最小割。处理的方法比较套路。而费用流的运行速度和$$simplex$$也差不了多少。无脑$$simplex$$。
//simplex
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#include<cmath>
#include<map>
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define mp(a,b) make_pair<int,int>(a,b)
#define cls(s) memset(s,0,sizeof(s))
#define cp pair<int,int>
#define LL long long int
using namespace std;
const int maxn = 25,maxm = 100005;
const double eps = 1e-8,INF = 1e15;
inline int read(){
int out = 0,flag = 1; char c = getchar();
while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}
while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}
return out * flag;
}
int n,m,id[maxn << 1];
double a[maxn][maxn],ans[maxn];
void Pivot(int l,int e){
swap(id[n + l],id[e]);
double t = a[l][e]; a[l][e] = 1;
for (int j = 0; j <= n; j++) a[l][j] /= t;
for (int i = 0; i <= m; i++) if (i != l && abs(a[i][e]) > eps){
t = a[i][e]; a[i][e] = 0;
for (int j = 0; j <= n; j++) a[i][j] -= a[l][j] * t;
}
}
bool init(){
while (true){
int e = 0,l = 0;
for (int i = 1; i <= m; i++) if (a[i][0] < -eps && (!l|| (rand() & 1))) l = i;
if (!l) break;
for (int j = 1; j <= n; j++) if (a[l][j] < -eps && (!e || (rand() & 1))) e = j;
if (!e){puts("Infeasible"); return false;}
Pivot(l,e);
}
return true;
}
bool simplex(){
while (true){
int l = 0,e = 0; double mn = INF;
for (int j = 1; j <= n; j++) if (a[0][j] > eps){e = j; break;}
if (!e) break;
for (int i = 1; i <= m; i++) if (a[i][e] > eps && a[i][0] / a[i][e] < mn)
mn = a[i][0] / a[i][e],l = i;
if (!l){puts("Unbounded"); return false;}
Pivot(l,e);
}
return true;
}
int main(){
srand(time(NULL));
n = read(); m = read(); int t = read();
REP(i,n) a[0][i] = read();
REP(i,m){
REP(j,n) a[i][j] = read();
a[i][0] = read();
}
REP(i,n) id[i] = i;
if (init() && simplex()){
printf("%.8lf\n",-a[0][0]);
if (t){
REP(i,m) ans[id[n + i]] = a[i][0];
REP(i,n) printf("%.8lf ",ans[i]);
}
}
return 0;
}
最小生成树
掌握$$Prim/Kruskal/Boruvka$$算法。
//Prim
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<sstream>
using namespace std;
typedef long long ll;
const int maxn = 2e3 + 10;
const int INF = 1 << 30;
int dir[4][2] = {1,0,0,1,-1,0,0,-1};
int T, n, m, x;
int Map[maxn][maxn];//存图
int lowcost[maxn], mst[maxn];
void prim(int u)//最小生成树起点
{
int sum_mst = 0;//最小生成树权值
for(int i = 1; i <= n; i++)//初始化两个数组
{
lowcost[i] = Map[u][i];
mst[i] = u;
}
mst[u] = -1;//设置成-1表示已经加入mst
for(int i = 1; i < n; i++)//此处只需要迭代n-1次即可
{
int minn = INF;
int v = -1;
//在lowcost数组中寻找未加入mst的最小值
for(int j = 1; j <= n; j++)
{
if(mst[j] != -1 && lowcost[j] < minn)
{
v = j;
minn = lowcost[j];
}
}
if(v != -1)//v=-1表示未找到最小的边,
{//v表示当前距离mst最短的点
printf("%d %d %d\n", mst[v], v, lowcost[v]);//输出路径
mst[v] = -1;
sum_mst += lowcost[v];
for(int j = 1; j <= n; j++)//更新最短边
{
if(mst[j] != -1 && lowcost[j] > Map[v][j])
{
lowcost[j] = Map[v][j];
mst[j] = v;
}
}
}
}
printf("weight of mst is %d\n", sum_mst);
}
int main()
{
cin >> n >> m;
memset(Map, 0, sizeof(Map));
for(int i = 1; i <= m; i++)
{
int u, v, w;
cin >> u >> v >> w;
Map[u][v] = Map[v][u] = w;
}
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
if(i == j)Map[i][j] = 0;
else if(!Map[i][j])Map[i][j] = INF;
}
}
prim(1);
return 0;
}
//kruskal
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,tot=0,k=0;//n端点总数，m边数，tot记录最终答案，k已经连接了多少边
int fat[200010];//记录集体老大
struct node
{
int from,to,dis;//结构体储存边
}edge[200010];
bool cmp(const node &a,const node &b)//sort排序（当然你也可以快排）
{
return a.dis<b.dis;
}
int father(int x)//找集体老大，并查集的一部分
{
if(fat[x]!=x)
return father(fat[x]);
else return x;
}
void unionn(int x,int y)//加入团体，并查集的一部分
{
fat[father(y)]=father(x);
}
int main()
{
scanf("%d%d",&n,&m);//输入点数，边数
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&edge[i].from,&edge[i].to,&edge[i].dis);//输入边的信息
}
for(int i=1;i<=n;i++) fat[i]=i;//自己最开始就是自己的老大 （初始化）
sort(edge+1,edge+1+m,cmp);//按权值排序（kruskal的体现）
for(int i=1;i<=m;i++)//从小到大遍历
{
if(k==n-1) break;//n个点需要n-1条边连接
if(father(edge[i].from)!=father(edge[i].to))//假如不在一个团体
{
unionn(edge[i].from,edge[i].to);//加入
tot+=edge[i].dis;//记录边权
k++;//已连接边数+1
}
}
printf("%d",tot);
return 0;
}
//broucvka解曼哈顿距离最大生成树
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<set>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int> abcd;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x){
char c=nc(),b=1;
for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;
for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;
}
const int N=100005;
const int dx[]={1,-1,1,-1};
const int dy[]={-1,-1,1,1};
set<abcd> Set[4];
int n; ll Ans=0;
int x[N],y[N];
ll a[N][4];
int fat[N];
#define pb push_back
vector<int> g[N];
inline int Fat(int u){
return fat[u]==u?u:fat[u]=Fat(fat[u]);
}
inline bool Merge(int x,int y){
x=Fat(x); y=Fat(y); if (x==y) return 0;
for (int i=0;i<(int)g[x].size();i++) g[y].pb(g[x][i]);
g[x].clear();
fat[x]=y; return 1;
}
struct edge{
int u,v,w;
edge(int u=0,int v=0,int w=0):u(u),v(v),w(w) { }
}ed[N];
int pnt=0;
int main(){
freopen("mst.in","r",stdin);
freopen("mst.out","w",stdout);
read(n);
for (int i=1;i<=n;i++){
read(x[i]); read(y[i]);
for (int j=0;j<4;j++){
a[i][j]=x[i]*dx[j]+y[i]*dy[j];
Set[j].insert(abcd(a[i][j],i));
}
}
for (int i=1;i<=n;i++) fat[i]=i,g[i].pb(i);
Ans=0;
while (1){
int flag=0; pnt=0;
for (int i=1;i<=n;i++){
if (fat[i]!=i) continue;
if (g[i].size()==n){
flag=1; break;
}
for (int j=0;j<(int)g[i].size();j++)
for (int k=0;k<4;k++)
Set[k].erase(abcd(a[g[i][j]][k],g[i][j]));
ll Max=-1LL<<40,v;
for (int k=0;k<4;k++){
ll maxu=-1LL<<40,maxv;
for (int j=0;j<(int)g[i].size();j++)
if (a[g[i][j]][k]>=maxu)
maxu=a[g[i][j]][k];
set<abcd>::iterator it=Set[k^3].end(); it--;
maxv=it->first;
if (maxu+maxv>=Max)
Max=maxu+maxv,v=it->second;
}
ed[++pnt]=edge(i,v,Max);
for (int j=0;j<(int)g[i].size();j++)
for (int k=0;k<4;k++)
Set[k].insert(abcd(a[g[i][j]][k],g[i][j]));
}
if (flag) break;
for (int j=1;j<=pnt;j++)
if (Merge(ed[j].u,ed[j].v))
Ans+=ed[j].w;
}
printf("%lld\n",Ans);
return 0;
}
套路1：
两点之间路径的边/点权的最大值最小（最小值最大）。
套路2：
动态维护最小生成树（加边/删边）
动态图中可以把每条边的删除时间当成边权维护最大生成树。
//魔法森林
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAXN = 50010;
const int MAXM = 100010;
const int MAXS = MAXN + MAXM;
const int INF = 1061109567;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
int x = 0; int w = 1; register char c = getchar();
for(; c ^ '-' && (c < '0' || c > '9'); c = getchar());
if(c == '-') w = -1, c = getchar();
for(; c >= '0' && c <= '9'; c = getchar()) x = (x<<3) + (x<<1) + c - '0'; return x * w;
}
struct Edge{
int x,y,a,b;
}e[MAXM];
int N,M,ans(INF),maxa;
int val[MAXS],mx[MAXS];
struct LinkCutTree{
int ch[MAXS][2],fa[MAXS];
bool tag[MAXS];
inline bool rson(int f, int x){
return ch[f][1] == x;
}
inline bool isroot(int x){
return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
}
inline void pushup(int x){
mx[x] = x;
if(val[mx[ch[x][0]]] > val[mx[x]]) mx[x] = mx[ch[x][0]];
if(val[mx[ch[x][1]]] > val[mx[x]]) mx[x] = mx[ch[x][1]];
}
inline void rotate(int x){
int f = fa[x], gf = fa[f];
bool p = rson(f,x), q = !p;
if(!isroot(f)) ch[gf][rson(gf,f)] = x; fa[x] = gf;
ch[f][p] = ch[x][q], fa[ch[x][q]] = f;
ch[x][q] = f, fa[f] = x;
pushup(f), pushup(x);
}
void reverse(int x){
if(!isroot(x)) reverse(fa[x]);
if(!tag[x]) return;
tag[x] = 0;
swap(ch[x][0], ch[x][1]);
tag[ch[x][0]] ^= 1, tag[ch[x][1]] ^= 1;
}
inline void splay(int x){
for(reverse(x); !isroot(x); rotate(x)){
if(isroot(fa[x])){ rotate(x); break; }
if(rson(fa[fa[x]],fa[x]) ^ rson(fa[x],x)) rotate(x); else rotate(fa[x]);
}
}
inline void access(int x){
for(int y = 0; x; y=x, x = fa[x]) splay(x), ch[x][1] = y, pushup(x);
}
inline void mroot(int x){
access(x), splay(x), tag[x] ^= 1;
}
inline int findroot(int x){
access(x), splay(x);
while(ch[x][0]) x = ch[x][0];
return x;
}
inline void split(int x, int y){
mroot(x);
access(y);
splay(y);
}
inline void link(int x, int y){
mroot(x);
fa[x] = y;
}
inline void cut(int x, int y){
split(x,y);
if(ch[y][0] != x || ch[x][1]) return;
ch[y][0] = fa[x] = 0;
}
}qxz;
inline bool cmp(const Edge& a, const Edge& b){
return a.a < b.a;
}
int main(){
// freopen(".in","r",stdin);
N = read(), M = read();
for(int i = 1; i <= M; ++i){
e[i].x = read(), e[i].y = read(), e[i].a = read(), e[i].b = read();
}
sort(e+1, e+M+1, cmp);
for(int i = 1; i <= M; ++i){
val[N+i] = e[i].b;
if(qxz.findroot(e[i].x) != qxz.findroot(e[i].y)){
qxz.link(e[i].x, N+i);
qxz.link(e[i].y, N+i);
maxa = e[i].a;
}
else{
qxz.split(e[i].x, e[i].y);
if(val[mx[e[i].y]] > e[i].b){
int temp = mx[e[i].y]-N;
qxz.cut(e[temp].x, temp+N);
qxz.cut(e[temp].y, temp+N);
qxz.link(e[i].x, N+i);
qxz.link(e[i].y, N+i);
maxa = e[i].a;
}
}
if(qxz.findroot(1) == qxz.findroot(N)){
qxz.split(1, N);
ans = Min(ans, maxa + val[mx[N]]);
}
}
if(ans == INF) printf("-1");
else printf("%d", ans);
return 0;
}
套路3：
完全图，每条边的边权为$$w(u)$$ $$op$$ $$w(v)$$。
一般来说可以用$$prim或者Boruvka$$。
最小树形图
掌握朱刘算法及输出方案。
//hdu 2121 Ice_cream’s world II
#include<iostream>
using namespace std;
#include<cstdio>
#include<cstring>
#define MAXN 1005
#define INF 0x7f7f7f7f
typedef __int64 type;
struct node//边的权和顶点
{
int u, v;
type w;
}edge[MAXN * MAXN];
int pre[MAXN], id[MAXN], vis[MAXN], n, m, pos;
type in[MAXN];//存最小入边权,pre[v]为该边的起点
type Directed_MST(int root, int V, int E)
{
type ret = 0;//存最小树形图总权值
while(true)
{
int i;
//1.找每个节点的最小入边
for( i = 0; i < V; i++)
in[i] = INF;//初始化为无穷大
for( i = 0; i < E; i++)//遍历每条边
{
int u = edge[i].u;
int v = edge[i].v;
if(edge[i].w < in[v] && u != v)//说明顶点v有条权值较小的入边 记录之
{
pre[v] = u;//节点u指向v
in[v] = edge[i].w;//最小入边
if(u == root)//这个点就是实际的起点
pos = i;
}
}
for( i = 0; i < V; i++)//判断是否存在最小树形图
{
if(i == root)
continue;
if(in[i] == INF)
return -1;//除了根以外有点没有入边,则根无法到达它 说明它是独立的点 一定不能构成树形图
}
//2.找环
int cnt = 0;//记录环数
memset(id, -1, sizeof(id));
memset(vis, -1, sizeof(vis));
in[root] = 0;
for( i = 0; i < V; i++) //标记每个环
{
ret += in[i];//记录权值
int v = i;
while(vis[v] != i && id[v] == -1 && v != root)
{
vis[v] = i;
v = pre[v];
}
if(v != root && id[v] == -1)
{
for(int u = pre[v]; u != v; u = pre[u])
id[u] = cnt;//标记节点u为第几个环
id[v] = cnt++;
}
}
if(cnt == 0)
break; //无环 则break
for( i = 0; i < V; i++)
if(id[i] == -1)
id[i] = cnt++;
//3.建立新图 缩点,重新标记
for( i = 0; i < E; i++)
{
int u = edge[i].u;
int v = edge[i].v;
edge[i].u = id[u];
edge[i].v = id[v];
if(id[u] != id[v])
edge[i].w -= in[v];
}
V = cnt;
root = id[root];
}
return ret;
}
int main()
{
int i;
while(scanf("%d%d", &n, &m) != EOF)
{
type sum = 0;
for( i = 0; i < m; i++)
{
scanf("%d%d%I64d", &edge[i].u, &edge[i].v, &edge[i].w);
edge[i].u++; edge[i].v++;
sum += edge[i].w;
}
sum ++;
for( i = m; i < m + n; i++)//增加超级节点0,节点0到其余各个节点的边权相同（此题中 边权要大于原图的总边权值）
{
edge[i].u = 0;
edge[i].v = i - m + 1;
edge[i].w = sum;
}
type ans = Directed_MST(0, n + 1, m + n);
//n+1为总结点数,m+n为总边数
//ans代表以超级节点0为根的最小树形图的总权值,
//将ans减去sum,如果差值小于sum,说明节点0的出度只有1,说明原图是连通图
//如果差值>=sum,那么说明节点0的出度不止为1,说明原图不是连通图
if(ans == -1 || ans - sum >= sum)
puts("impossible");
else
printf("%I64d %d\n",ans - sum, pos - m);
puts("");
}
return 0;
}
$$Steiner Tree$$
掌握$$O(3{kn}+2{kmlog(m)} )$$的方法。
//POJ3123
#include <iostream>
#include <string>
#include <map>
using namespace std;
int main()
{
int INF = 99999999, N, K, d[30][30], i, j, k, x, y, z;
int dp[256][30], e[8], v[30], c, b;
string s, t;
while (cin >> N >> K && N)
{
map <string, int> cityMap;
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
d[i][j] = i == j ? 0 : INF;
for (i = 0; i < N; i++)
{
cin >> s;
cityMap[s] = i;
}
if (K)
while (cin >> s >> t >> z, x = cityMap[s],
y = cityMap[t],
d[x][y] = d[y][x] = min(d[y][x], z), --K);
for (k = 0; k < N; k++)
for (i = 0; i < N; i++)
for (j = 0; j < N; j++)
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
for (i = 0; i < 8; i++)
{
cin >> s;
e[i] = cityMap[s];
for (j = 0; j < N; j++)
dp[1 << i][j] = d[j][e[i]];
}
for (i = 1; i < 256; i++)
{
if (!(i & (i - 1)))
continue;
// step1
for (k = 0; k < N; k++)
{
dp[i][k] = INF;
v[k] = 0;
/*for (j = 1; j < i; j++)
if ((i | j) == i)
dp[i][k] = min(dp[i][k], dp[j][k] + dp[i-j][k]);*/
for (int sub = i; sub; sub = (sub - 1) & i)
{
dp[i][k] = min(dp[i][k], dp[sub][k] + dp[i - sub][k]);
}
}
// step2
for (j = 0; b = INF, j < N; j++)
{
for (k = 0; k < N; k++)
if (dp[i][k] <= b && !v[k])
b = dp[i][c = k];
for (k = 0, v[c] = 1; k < N; k++)
dp[i][c] = min(dp[i][c], dp[i][k] + d[k][c]);
}
}
// step3
for (i = 0, b = INF; z = 0, i < 256; b = min(b, z), i++)
for (j = 0; y = 0, j < 4; z += !!y * dp[y][x], j++)
for (k = 0; k < 8; k += 2)
if ((i >> k & 3) == j)
y += 3 << k, x = e[k];
cout << b << endl;
}
return 0;
}
二分图匹配
一般结果只与$$x，n-x，m-x，n+m-x $$有关。
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define maxn 20000+200
using namespace std;
inline int read(){
register int x=0,y=0;register char ch=getchar();
for(;!isdigit(ch);ch=getchar())if(ch=='-')y=1;
for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
return y?-x:x;
}
struct edge{
int v,n;
}e[maxn];
int first[maxn],ask[maxn],matched[maxn];
int n,m,er,ans=0,num_edge=0;
inline void add(int u,int v){
int k=++num_edge;
e[k].n=first[u],first[u]=k,e[k].v=v;
}
int found(int x){
int ee,v;
for(ee=first[x];v=e[ee].v,ee;ee=e[ee].n)
if(!ask[v]){
ask[v]=1;
if(!matched[v]||found(matched[v]))
matched[v]=x;return 1;
}
return 0;
}
inline void match(){
int cnt=0;
memset(matched,0,sizeof(matched));
for(int i=1;i<=n;++i){
memset(ask,0,sizeof(ask));
if(found(i))++cnt;
}
ans=cnt;
}
signed main(){
n=read(),m=read(),er=read();
int x,y;
for(int i=1;i<=er;++i)
{
if(x>n||y>m)continue;
x=read(),y=read(),
add(x,y);
}
match();
printf("%d\n",ans);
return 0;
}
仙人掌
任意一条边至多只出现在一条简单回路的无向连通图称为仙人掌。
//luogu-P5236
#include<bits/stdc++.h>
#define N 10005
#define M 80005
using namespace std;
inline void rd(int &X){
X=0;char ch=0;
while(!isdigit(ch))ch=getchar();
while( isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
}
int n,m,q,cnt=1,tot,num;
int head[N],dis[N],v[N];
struct nd{int nxt,to,v;}e[M];
int d[N],Dis[N],vis[M],pre[N],sum[M],c[N],f[N][15];
#define For(x) for(int y,i=head[x];(y=e[i].to);i=e[i].nxt)
inline void add(int x,int y,int v){
e[++cnt]={head[x],y,v};head[x]=cnt;
e[++cnt]={head[y],x,v};head[y]=cnt;
}
void SPFA(){
queue<int> q;q.push(1);
memset(dis,0x3f,sizeof dis);dis[1]=dis[0]=0;
while(q.size()){
int x=q.front();q.pop();v[x]=0;
For(x) if(dis[y]>dis[x]+e[i].v){
dis[y]=dis[x]+e[i].v;
if(!v[y]) v[y]=1,q.push(y);
}
}
}
void work(int x,int rt){
if(x==rt) return ;
add(rt,x,0);vis[pre[x]]=vis[pre[x]^1]=1;
sum[num]+=e[pre[x]].v;c[x]=num;work(e[pre[x]^1].to,rt);
}
void dfs(int x){
v[x]=++tot;
For(x) if(i^pre[x]^1)
if(!v[y]) pre[y]=i,Dis[y]=Dis[x]+e[i].v,dfs(y);
else if(v[y]<v[x]) {
sum[++num]=e[i].v;
vis[i]=vis[i^1]=1; work(x,y);
}
}
void dfs2(int x){
for(int i=1;i<=14;i++)
f[x][i]=f[f[x][i-1]][i-1];
For(x) if(!vis[i] and y!=f[x][0])
d[y]=d[x]+1,f[y][0]=x,dfs2(y);
}
int ask(int x=0,int y=0){
rd(x);rd(y);
if(d[x]<d[y]) swap(x,y);
int X=x,Y=y;
for(int i=14;~i;i--)
if(d[f[x][i]]>=d[y])
x=f[x][i];
if(x==y) return dis[X]-dis[Y];
for(int i=14;~i;i--)
if(f[x][i]!=f[y][i])
x=f[x][i],y=f[y][i];
if(c[x] and c[x]==c[y]){
int now=sum[c[x]],L=abs(Dis[x]-Dis[y]);
return min(L,now-L)+dis[X]-dis[x]+dis[Y]-dis[y];
}return dis[X]+dis[Y]-2*dis[f[x][0]];
}
signed main(){
rd(n);rd(m);rd(q);
for(int x,y,v,i=1;i<=m;i++)
rd(x),rd(y),rd(v),add(x,y,v);
SPFA();dfs(1);dfs2(1);
while(q--) printf("%d\n",ask());
}
平面图
对于一个图G=< V,E >,如果能把G画在一个平面上,且画出的图的任意两条边除了V中的节点没有其他交点,则图G为平面图.
//HNOI2010 Planar平面图判定
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int MAXE=10010;
const int MAXV=300;
struct node
{
int x,y;
}e2[MAXE];
int test,n,m,sum;
int h[MAXV],rank[MAXV],c[MAXV];
bool map[MAXV][MAXV],flag;
vector<int> e[MAXE],dag[MAXE];
vector<int>::iterator it;
bool Fright(int x1,int y1,int x2,int y2)
{
if (x1==x2 || x1==y2 || y1==x2 || y1==y2) return 0;
x1=rank[x1],y1=rank[y1];
x2=rank[x2],y2=rank[y2];
if (x1>y1) swap(x1,y1);
return (x1<x2 && x2<y1)!=(x1<y2 && y2<y1);
}
void Colour(int v,int x)
{
c[v]=x;
int size=dag[v].size();
for (int i=0;i<size;++i)
{
if (!c[dag[v][i]]) Colour(dag[v][i],-x); else
if (c[dag[v][i]]==x) flag=0;
if (!flag) return;
}
}
int main()
{
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
scanf("%d",&test);
while (test--)
{
scanf("%d%d",&n,&m);
flag=1;
for (int i=1;i<=n;++i) e[i].clear();
for (int i=1;i<=m;++i)
{
int x,y;
scanf("%d%d",&x,&y);
e[x].push_back(y);
}
for (int i=1;i<=n;++i)
scanf("%d",&h[i]),rank[h[i]]=i;
memset(map,0,sizeof(map));
for (int i=2;i<=n;++i)
map[h[i-1]][h[i]]=map[h[i]][h[i-1]]=1;
map[h[n]][h[1]]=map[h[1]][h[n]]=1;
if (m>n*3-6)
{
printf("NO\n");
continue;
}
sum=0;
for (int i=1;i<=n;++i)
for (it=e[i].begin();it<e[i].end();++it)
if (!map[i][*it]) e2[++sum].x=i,e2[sum].y=*it;
for (int i=1;i<=sum;++i) dag[i].clear();
for (int i=1;i<=sum;++i)
for (int j=i+1;j<=sum;++j)
if (Fright(e2[i].x,e2[i].y,e2[j].x,e2[j].y)) dag[i].push_back(j),dag[j].push_back(i);
memset(c,0,sizeof(c));
for (int i=1;i<=sum;++i)
if (!c[i])
{
Colour(i,1);
if (!flag) break;
}
if (flag) printf("YES\n"); else printf("NO\n");
}
return 0;
}
