图算法之个人整理总结.doc

陈江勇整理 2025-8-26
图算法实例

1. Dijkstra算法求最短路算法 2
2. 求所有点最短路的Dijkstra算法 3
3. 欧拉路径 4
4. 最大的流 8
5. 有向图的强连通分量和2-sat的判定问题 10
6. 求图中不含有割点（关结点）的块 18
7. 图的奇环的判断,是否为二分图的判断 19
8. 二分图的匹配 20
9. prim算法求最小生成树 20
10. 给有有向图最少加边使图中没有桥 21
11. 套汇问题 24
12. 差分系统 24
13. 二分图加权匹配--KM算法 32
14. floyed算法 36

1. Dijkstra算法求最短路算法
用堆来实现
输入输出说明：
N , M 然后
M 条边即相应的边的长
2 2
1 2 5
2 1 4
#include
#include
#include
#include
using namespace std;
#define INF INT_MAX
#define maxn 30000
struct NODE
{
int v;
int weight;
};
int wt[maxn],heap[maxn*2],r,N,M; //wt[i]保存从开始节点到节点i的最短路，heap的大小不确定
bool visit[maxn]; //一般开到节点数目两到三倍。这是因为堆中会有相同的节点，但他们的权重
vectorG[maxn]; //不一样
int cmp(int a,int b)
{
return wt[a]>wt[b];
}
int dijkstra(int s,int t)
{
int i,u;
for(i=0;i
heap[r]=s;
wt[s]=0;
r++;
memset(visit,0,sizeof(visit));
while(r>=0)
{
u=heap[0];
pop_heap(heap,heap+r,cmp);
r--;
if(visit[u])
{
continue;
}
visit[u]=1;
if(u==t)
{
return wt[t];
}
for(i=0;i][i].v]) //发现更好的状态但是堆可能已经存在
{ //编号为v的节点状态。
wt[G[u][i].v]=wt[u]+G[u][i].weight;
heap[r]=G[u][i].v;
r++;
push_heap(heap,heap+r,cmp);
}
}
}
return -1;
}
int main()
{
NODE temp;
int i,A,B,c;
scanf("%d%d",&N,&M);
for(i=0;i"%d%d%d",&A,&B,&c);
temp.v=A-1;
temp.weight=c;
G[B-1].push_back(temp);
}
printf("%d\n",dijkstra(N-1,0));
return 1;
}
2. 求所有点最短路的Dijkstra算法
void dijkstra(int s)
{
int i,u,j,min;
memset(visit,0,sizeof(visit));
for(i=1;i<=F;i++)
{
if(G[s][i]) //存在着边
{
dist[i]=G[s][i];
}
else
{
dist[i]=INT_MAX;
}
}
dist[s]=0;
visit[s]=1;
for(i=1;i<=F;i++)
{
u=-1;
min=INT_MAX;
for(j=1;j<=F;j++)
{
if(dist[j]
{
if(G[u][j]&&!visit[j]&&dist[j]>dist[u]+G[u][j])
{
dist[j]=dist[u]+G[u][j];
}
}
}
}
3. 欧拉路径
判断欧拉路径时要注意有向图无图的区别。
以下是链表形式
struct NODE
{
int v,id;
NODE *next;
};
void path(int u,int id)
{
link p;
int vv,dd;
while(adj[u])
{
p=adj[u];
vv=p->v;
dd=p->id;
adj[u]=p->next;
delete p;
path(vv,dd);
}
ans[top++]=id;
}
注意这边ans是反序存结果。

Sample Input

2
6
aloha
arachnid
dog
gopher
rat
tiger
3
oak
maple
elm

Sample Output

aloha.arachnid.dog.gopher.rat.tiger
***

#include
#include
#include
using namespace std;
#define maxn 1024
bool cmp(string a,string b)
{
return a>b;
}
struct NODE
{
int v,id;
NODE *next;
};
typedef NODE *link;
int ans[maxn],top,in[32],out[32],start;
string save[maxn];
link adj[32];
void insert(int u,int v,int id)
{
link p=new NODE;
p->v=v;
p->id=id;
p->next=adj[u];
adj[u]=p;
}
void path(int u,int id)
{
link p;
int vv,dd;
while(adj[u])
{
p=adj[u];
vv=p->v;
dd=p->id;
adj[u]=p->next;
delete p;
path(vv,dd);
}
ans[top++]=id;
}
int check()
{
int i,e1,e2,cnt;
e1=e2=cnt=0;
for(i=0;i<26;i++)
{
if(out[i]-in[i]==1)
{
start=i;
e1++;
cnt++;
}
else if(in[i]-out[i]==1)
{
e2++;
cnt++;
}
else if(in[i]!=out[i])
{
return 0;
}
}
if(!(cnt==2||cnt==0))
{
return 0;
}
if(cnt==2&&e1!=1)
{
return 0;
}
if(cnt==0)
{
for(i=0;i<26;i+)
{
if(out[i])
{
start=i;
break;
}
}
}
return 1;
}
int main()
{
int T,N,i,a,b;
cin>>T;
while(T--)
{
cin>>N;
for(i=0;i>save[i];
}
sort(save,save+N,cmp);
memset(adj,0,sizeof(adj));
memset(in,0,sizeof(in));
memset(out0,sizeof(out));
for(i=0;i
}
else
{
for(i=top-2;i>0;i--)
{
cout<f,r,v;
memset(pre,-1,sizeof(pre));
f=r=0;
Q[r++]=s;
while(f
return 1;
}
}
}
}
return 0;
}
int max_flow(int s,int t)
{
int p,ans=0,d;
while(BFS(s,t))
{
d=INF;
for(p=t;p!=s;p=pre[p])
{
if(G[pre[p]][p] d=G[pre[p]][p];
}
}
ans+=d;
for(p=t;p!=s;p=pre[p])
{
G[pre[p]][p]-=d;
G[p][pre[p]]+=d;
}
}
return ans;
}
5. 有向图的强连通分量和2-sat的判定问题
#include
#include
using namespace std;
#define INF 102400
#define maxn 1024*2
int low[maxn*2],cnt,cnt1,stack[maxn*2],top,sc[maxn*2],N,M,flag;
int visit[maxn*2]={0};
vectorG[maxn*2];
void DFS(int u)
{
int i,len,min,v;
visit[u]=flag;
len=G[u].size();
min=low[u]=cnt++;
stack[top++]=u;
for(i=0;iflag)
{
DFS(G[u][i]);
}
if(min>low[G[u][i]])
{
min=low[G[u][i]];
}
}
if(min
if(visit[i]!=flag)
{
top=0;
DFS(i);
}
}
for(i=0;i有 M行，表示需要 X或者 Y钥匙
输出：
最多可以打开的门的数量。
Sample Input
3 6
0 3
1 2
4 5
0 1
0 2
4 1
4 2
3 5
2 2
0 0
Sample Output
4

每把钥匙都对应一个变量A和~A
算法，本题采用2-sat算法，通过求强连通分量来求解。

以下是代码的解释：
for(i=1;i<=n;i++)
{
scanf("%d%d",&a,&b);
G[a].push_back(b+N); 由于每把钥匙不能同时都用所以~(A^B) ~A∨~B
G[b].push_back(a+N); Aà~B Bà~A (即A和B不能同
} 时为1）
ans=0;
for(i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
G[a+N].push_back(b); //两把钥匙，选一就可以开门了，X∨Y ~XàY
G[b+N].push_back(a); // ~YàX
flag++;
if(!check())
{
break;
}
else
{
ans=i;
}
}
题目意思：
Farmer john要用两个中转站把所有的农场连起来，但是有些农场的牛互相恨对方，不能将这些农场连在同一个中转站，有些农场的牛是朋友
必须将这些农场连在同一个农场。现在问你通过某种方案相连后，距离最远的两个农场的最小距离是多少。
Sample Input

4 1 1
12750 28546 15361 32055
6706 3887
10754 8166
12668 19380
15788 16059
3 4
2 3

Sample Output

53246

解题报告：
标程用的算法是二分查找，给定一个答案后，用2-SAT判断是否可行。下面主要说一下2-SAT问题的建模。用布尔变量Xi表示第i个牛栏连到第一个中转站，即Xi为真时连到第一个，为假时连到第二个。那么~Xi表示第i个牛栏连到第二个中转站，~表示布尔取反。 检查每一个约束条件，构造2-SAT的和取范式。

1）i和j不连到同一个中转站，就增加和取范式(Xi + Xj)(~Xi + ~Xj)。

2）i和j必须连到同一个中转站，就增加和取范式(Xi + ~Xj)(~Xi + Xj)。

设现在二分的答案是S。那么检查每一对牛栏i和j（假设D1i，D1j表示i和j到第一个中转站的距离，D2i，D2j表示i和j到第二个中转站的距离，DD表示两个中转站之间的距离）。如果

3）D1i + D1j 〉S，就增加和取范式（~Xi + ~Xj）

4）D2i + D2j 〉S，就增加和取范式（Xi + Xj）

5）D1i + D2j + DD 〉S，就增加和取范式（~Xi + Xj）

6）D2i + D1j + DD 〉S，就增加和取范式（Xi + ~Xj）

剩下的只是用2-SAT的现成算法去判断是否有解。
#include
#include
#include
#define maxn 500
int G[maxn*2][maxn*2],en[maxn*2]={0},tn[maxn*2];
int dis[maxn][2],sc[maxn*2],lw[maxn*2],stack[maxn*2],top;
bool visit[maxn*2];
int N,A,B,low,high,sx1,sy1,sx2,sy2,DS,cnt,cnt1;
inline int abs(int a)
{
return a>0?a:-a;
}
inline void insert(int a,int b)
{
G[a][en[a]++]=b;
}
void DFS(int u)
{
visit[u]=1;
stack[top++]=u;
lw[u]=cnt++;
int min=lw[u];
int i;
for(i=0;ilw[G[u][i]])
{
min=lw[G[u][i]];
}
}
if(minnt v;
do
{
sc[v=stack[--top]]=cnt1;
lw[v]=INT_MAX;
}while(v!=u);
cnt1++;
}
int add_edge(int dd)
{
int i,j,f;
for(i=0;idd)
{
f++;
insert(i,j+N);
insert(j,i+N);
}
if(dis[i][1]+dis[j][1]>dd)
{
f++;
insert(i+N,j);
insert(j+N,i);
}
if(dis[i][0]+dis[j][1]+DS>dd)
{
f++;
insert(i,j);
insert(j+N,i+N);
}
if(dis[i][1]+dis[j][0]+DS>dd)
{
f++;
insert(j,i);
insert(i+N,j+N);
}
if(f>=4)
{
return 0;
}
}
}
return 1;
}
int check()
{
int i;
cnt=cnt1=1;
memset(visit,0,sizeof(visit));
for(i=0;i<2*N;i++)
{
if(!visit[i])
{
DFS(i);
}
}
for(i=0;id%d",&N,&A,&B);
scanf("%d%d%d%d",&sx1,&sy1,&sx2,&sy2);
DS=abs(sx1-sx2)+abs(sy1-sy2);
low=INT_MAX;
high=-INT_MAX;
for(i=0;ihigh)
{
high=dis[i][0];
}
if(dis[i][1]>high)
{
high=dis[i][1];
}
if(dis[i][0])
{
scanf("%d%d",&a,&b);
a--,b--;
insert(a,b);
insert(b,a);
insert(a+N,b+N);
insert(b+N,a+N);
}
if(!check())
{
printf("-1\n");
return 1;
}
low*=2;
high=high*2+DS;
for(i=0;i<2*N;i++)
{
tn[i]=en[i];
}
while(lowen,tn,sizeof(int)*2*N);
if(add_edge(mid)&&check())
{
high=mid;
}
else
{
low=mid+1;
}
}
printf("%d\n",high);
return 1;
}
关键部分说明：
for(i=0;insert(a+N,b); (a∨b)^(~a∨~b)有a-->~b,b-->~a,~a-->b
insert(b+N,a); //_b-->a
}
for(i=0;ib,~b-->`~a,b-->a, ~a-->~b
insert(a+N,b+N);
insert(b+N,a+N);
}
6. 求图中不含有割点（关结点）的块
void dfs(int u,int father)
{
int v,t;
pre[u]=low[u]=cnt++;
stack[top++]=u;
for(v=0;v=pre[u])
{
do
{
t=stack[--top];
save[k++]=t;
}while(t!=v);
save[k++]=u;
check(); //这个函数处理save中块的结点函数，处理完后k=0
}
}
else if(low[u]>pre[v])
{
low[u]=pre[v];
}
}
}
}
void solve()
{
cnt=top=0;
int i,ans=0;
for(i=0;i1)
{
dfs(i,-1);
}
}
}

要正确区别不含关结点的块和（有向图或无向图）的强连通分量的区别，也就是要区别双向连通性和边连通性，双向连通任何两个结点存在两条不共用结点的路径，边连通性则不共用边,可以共用结点。

1
4

3
5
2
右边这个图有两个块：
5
4
3
2
3
1
如下面的图所示：

7. 图的奇环的判断,是否为二分图的判断

bool color(int u,int c)
{
int v;
cor[u]=c;
for(v=0;v);v++)
{
if(cor[G[u][v]]==-1)
{
if(!color(G[u][v],1-c))
return false;
}
else if(cor[G[u][v]]==c)
{
return false;
}
}
return true;
}
memset(cor,-1,sizeof(cor));
color(0,1);
8. 二分图的匹配
一个G[N][M]的图的匹配，当图的边很少时，可以采用链表来做。
int my[M],visit[M];
int path(int u)
{
int i;
for(i=0;ih(i);
}
return cnt;
}
9. prim算法求最小生成树
int G[maxn][maxn]={0},wt[maxn],N,st[maxn],fr[maxn];
void GRAPHmstV(int st[],int wt[]) //节点编号为0到N-1
{ //wt[i] 若i未加入生成树中，表示结点i到生成树中结点的最小距离。
int v,w,min; //st[]有两个作用，初始st[]为-1可以作是否访问的标记，最后i--st[i]为所求最小
for(v=0;vv]=-1;
fr[v]=v;
wt[v]=INT_MAX;
}
st[0]=0; //初始0为
wt[N]=INT_MAX;
for(min=0;min!=N;)
{
v=min;
st[min]=fr[min];
for(w=0,min=N;w
}
if(wt[w]e
#include
#include
using namespace std;
vectorG[5001];
int stack[5001],N,low[5001],sc[5001],cnt,cnt1;
bool visit[5001];
void dfs(int father,int u) //这边多了一个father参数的作用要注意
{ //与有向图的的强连通分量的求法有所不同
int i,len,min,v;
len=G[u].size();
visit[u]=1;
stack[N++]=u;
low[u]=cnt++;
min=low[u];
for(i=0;ilow[v])
{
min=low[v];
}
}
}
if(min000;
}while(v!=u);
cnt1++;
}
}
int main()
{
int N,M,i,a,b,j;
scanf("%d%d",&N,&M);
for(i=1;i<=M;i++)
{
scanf("%d%d",&a,&b);
for(j=0;j);
}
cnt=cnt1=1;
dfs(0,1);
vector::iterator p;
memset(stack,0,sizeof(stack));
for(i=1;i<=N;i++)
{
// printf("%d\n",sc[i]);
for(p=G[i].begin();p!=G[i].end();p++)
{
if(sc[i]!=sc[*p])
{
// printf("%d %d\n",sc[i],sc[*p]);
stack[sc[i]]++;
}
}
}
int ans=0;
for(i=1;i0)
{
for(j=0;j][k]*rate[k][j]>rate[i][j])
{
rate[i][j]=rate[i][k]*rate[k][j];
}
}
}

}
}
}
bool check()
{
int i;
for(i=0;i1)
{
return true;
}
}
return false;
}
12. 差分系统

注意差分系统只能处理x1>=x2+3, x3>=x4+5……等（或把大于等于改成小于等于）只能是大于等于或小于等