图论Word格式.docx
- 文档编号:5698399
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:36
- 大小:25.60KB
图论Word格式.docx
《图论Word格式.docx》由会员分享,可在线阅读,更多相关《图论Word格式.docx(36页珍藏版)》请在冰点文库上搜索。
A+B+C/a+b
拓扑排序
structphoto{
intn;
intum;
inttot;
intYd[N];
inttops[N];
queue<
int>
que;
photo(){
tot=0;
memset(Yd,0,sizeof(Yd));
E.clear();
for(inti=1;
i<
N;
++i)edge[i].clear();
}
vector<
E;
edge[N];
voidaddp(intu,intv){
edge[u].push_back(v);
Yd[v]++;
voidaddnp(inta,intb){
addp(a,b);
addp(b,a);
voidtopsort(){
=n;
++i)
if(!
Yd[i])tops[++um]=i,que.push(i);
while(!
que.empty()){
inttop=que.front();
que.pop();
for(inti=0;
edge[top].size();
++i){
ints=edge[top][i];
Yd[s]--;
if(!
Yd[s]){
tops[++um]=s;
que.push(s);
}
}
}
}VE;
拓扑排序计数
给定一个图,求拓扑排序的方案总数。
保证答案不超过10^5。
保证答案不超过10^18。
按照拓扑序枚举每个点,dp[i]=sigma_{j->
i}dp[j]
intD[N];
E[N];
D[v]++;
voidaddq(intu,intv){
E[v].push_back(u);
longlongans(intsdf){
D[i]){dp[i]++;
continue;
}
for(intj=0;
j<
E[i].size();
++j)
dp[i]+=dp[j];
returndp[sdf];
求“割点”给定一张n个点m条边的拓扑图(保证1号点能走到n号点),求存在多少点,将其删去后1号点走不到n号点。
n,m<
令f[i]表示1号点走到i号点的方案总数
g[i]表示n号点反着走到i号点的方案总数
i是割点当且仅当f[i]*g[i]=f[n]
利用上面的求方案总数可以做出这道题
Dijkstra不适用于负边权
SPFA适用于负边权
SPFA判断是否存在负环如果一个点进入队列超过n次,这个图一定存在负环
二分图
如果一个无向图G中V能分成两个点集A与B,且位于A中的顶点互相之
间没有边,位于B中的顶点互相之间没有边,则称这个图为二分图。
判定二分图的方法
1.DFS二分图染色
2.拆点并查集维护
#include<
iostream>
cstdio>
usingnamespacestd;
structedge{
intv,next;
}e[N];
inthead[N],sum,n,m;
voidadd(inta,intb){
e[++sum].v=b;
e[sum].next=head[a];
head[a]=sum;
voidpush(inta,intb){
add(a,b);
add(b,a);
voidNO(){
cout<
<
"
NO"
;
exit(0);
intchangecolor(intcolor){
if(color==2)return1;
elsereturn2;
voiddfs(ints.intcolor){
col[s]=color;
intco=changecolor(color);
for(inti=head[s];
i;
i=e[i].next){
intv=edge[i].v;
intcv=col[v];
if(cv==color)NO();
if(!
cv)dfs(v,cv);
拆点并查集
intfind(intson){
if(fa[son]==son)
fa[son]=find(fa[son]);
returnfa[son];
voidun(inta,intb){
a=find(a);
b=find(b);
fa[a]=b;
intmain(){
intn,m;
cin>
>
n>
m;
for(inti=1;
++i)fa[i]=i;
=m;
inta,b;
cin>
a>
b;
un(a,b+n);
un(a+n,b);
if(find(a)==find(a+n))NO();
if(find(b)==find(b+n))NO();
return0;
最大边权最小的生成树为最小生成树
最小生成树不仅可以得到最小的权值之和,其最大边权为生成树中最大边权最小的。
1:
承包池塘的青蛙
查看提交统计提问
总时间限制:
1000ms内存限制:
128000kB
描述
某池塘有N片荷叶,M只青蛙,青蛙喜欢在荷叶之间跳来跳去.
给出青蛙们的最大可跳跃的距离Ci,以及荷叶的坐标,当忽略荷叶的直径.如果两片荷叶A和B间的距离小于某只青蛙F的最大可跳跃距离时,可认为青蛙F可以从A跳到B,也可以从B跳到A.
求能够从任意荷叶出发,仅通过跳跃就能到达其它任意荷叶的青蛙个数.
输入
第一行一个整数,表示M(2<
=M<
=500)
第二行为M个整数,依次表示Ci(每个整数值在1—1000之间)
第三行为一个整数,表示N(2<
=N<
=1000)
第四行至第N+3行,每行两个数,分布表示N个荷叶的坐标(横纵坐标均为整数,范围为:
-10000–10000)
输出
输出只有一行,即所求满足条件的青蛙只数.
样例输入
4
100200300400
6
00
1000
100200
-100-100
-2000
200200
样例输出
3
最小生成树的最长边即是青蛙跳跃的最长距离
cstdlib>
algorithm>
structnode
{
inta,b,dis;
}s[1500];
intsum=1,n,fa[1500];
boolcmp(nodea,nodeb)
returna.dis<
b.dis;
intfind(intson)
if(fa[son]!
=son)
fa[son]=find(fa[son]);
intmain()
intans=0;
n;
for(intj=1;
{
s[sum].a=i;
s[sum].b=j;
s[sum++].dis;
sort(s+1,s+sum,cmp);
intk=0;
intr1=find(s[i].a);
intr2=find(s[i].b);
if(find(s[i].a)!
=find(s[i].b))
fa[r2]=r1;
ans=max(ans,s[i].dis);
k++;
if(k==n-1)
break;
ans;
二分图最大匹配
匈牙利算法
structEdge{
intfrom,to;
intweight;
Edge(intf,intt,intw):
from(f),to(t),weight(w){}
};
vector<
G[__maxNodes];
Edge>
edges;
typedefvector<
:
iteratoriterator_t;
intnum_nodes;
intnum_left;
intnum_right;
intnum_edges;
intmatching[__maxNodes];
intcheck[__maxNodes];
DFS:
booldfs(intu){
for(iterator_ti=G[u].begin();
i!
=G[u].end();
++i){
intv=edges[*i].to;
if(!
check[v]){
check[v]=true;
if(matching[v]==-1||dfs(matching[v])){
matching[v]=u;
matching[u]=v;
returntrue;
}
returnfalse;
}
inthungarian(){
memset(matching,-1,sizeof(matching));
for(intu=0;
u<
num_left;
++u){
if(matching[u]==-1){
memset(check,0,sizeof(check));
if(dfs(u))
++ans;
returnans;
Kuhn-Munkres算法求解带权二分图匹配
cstring>
#defineMAX1300
intn;
intweight[MAX][MAX];
intlx[MAX],ly[MAX];
boolsx[MAX],sy[MAX];
intmatch[MAX];
voidinit(intsize){
n=size;
for(inti=0;
i++)
for(intj=0;
j++)
scanf("
%d"
&
weight[i][j]);
boolpath(intu){
sx[u]=true;
for(intv=0;
v<
v++)
if(!
sy[v]&
&
lx[u]+ly[v]==weight[u][v]){
sy[v]=true;
if(match[v]==-1||path(match[v])){
match[v]=u;
intbestmatch(boolmaxsum)
{
inti,j;
maxsum){
for(i=0;
for(j=0;
weight[i][j]=-weight[i][j];
i++){
lx[i]=-0x1FFFFFFF;
ly[i]=0;
if(lx[i]<
weight[i][j])
lx[i]=weight[i][j];
memset(match,-1,sizeof(match));
for(intu=0;
u++)
while(true){
memset(sx,0,sizeof(sx));
memset(sy,0,sizeof(sy));
if(path(u))
intdx=0x7FFFFFFF;
if(sx[i])
sy[j])
dx=min(lx[i]+ly[j]-weight[i][j],dx);
lx[i]-=dx;
if(sy[i])
ly[i]+=dx;
intsum=0;
sum+=weight[match[i]][i];
sum=-sum;
returnsum;
intmain()
n);
init(n);
intcost=bestmatch(true);
printf("
%d"
cost);
%d%d\n"
i,match[i]);
最小费用最大流求解带权二分图最大匹配问题
vector>
queue>
#defineN10005
#defineINF0x3f3f3f3f
intfrom,to,cap,flow,cost;
Edge(intu,intv,intca,intf,intco):
from(u),to(v),cap(ca),flow(f),cost(co){};
structMCMF{
intn,m,s,t;
G[N];
intinq[N];
intd[N];
intp[N];
inta[N];
voidinit(intn){
this->
n=n;
G[i].clear();
edges.clear();
voidaddedge(intfrom,intto,intcap,intcost){
edges.push_back(Edge(from,to,cap,0,cost));
edges.push_back(Edge(to,from,0,0,-cost));
intm=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
boolSPFA(ints,intt,int&
flow,int&
cost){
d[i]=INF;
memset(inq,0,sizeof(inq));
d[s]=0;
inq[s]=1;
p[s]=0;
a[s]=INF;
Q;
Q.push(s);
while(!
Q.empty()){
intu=Q.front();
Q.pop();
inq[u]--;
G[u].size();
Edge&
e=edges[G[u][i]];
if(e.cap>
e.flow&
d[e.to]>
d[u]+e.cost){
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap-e.flow);
inq[e.to]){
inq[e.to]++;
Q.push(e.to);
if(d[t]==INF)returnfalse;
flow+=a[t];
cost+=d[t]*a[t];
intu=t;
while(u!
=s){
edges[p[u]].flow+=a[t];
edges[p[u]^1].flow-=a[t];
u=edges[p[u]].from;
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图论
![提示](https://static.bingdoc.com/images/bang_tan.gif)