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

陈江勇整理2020-2-1图算法实例1.Dijkstra算法求最短路算法22.求所有点最短路的Dijkstra算法33.欧拉路径44.最大的流85.有向图的强连通分量和2-sat的判定问题106.求图中不含有割点（关结点）的块187.图的奇环的判断,是否为二分图的判断198.二分图的匹配209.prim算法求最小生成树2010.给有有向图最少加边使图中没有桥2111.套汇问题2412.差分系统2413.二分图加权匹配-KM算法3214.floyed算法361. Dijkstra算法求最短路算法用堆来实现输入输出说明：N , M 然后M 条边即相应的边的长2 21 2 52 1 4#include#include#include#includeusing namespace std;#define INF INT_MAX#define maxn 30000struct NODEint v;int weight;int wtmaxn,heapmaxn*2,r,N,M; /wti保存从开始节点到节点i的最短路，heap的大小不确定bool visitmaxn; /一般开到节点数目两到三倍。这是因为堆中会有相同的节点，但他们的权重vectorGmaxn; /不一样int cmp(int a,int b)return wtawtb;int dijkstra(int s,int t)int i,u;for(i=0;i=0)u=heap0;pop_heap(heap,heap+r,cmp);r-;if(visitu)continue;visitu=1;if(u=t)return wtt;for(i=0;iGu.size();i+)if(wtu+Gui.weightwtGui.v) /发现更好的状态但是堆可能已经存在 /编号为v的节点状态。wtGui.v=wtu+Gui.weight;heapr=Gui.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;iM;i+)scanf(%d%d%d,&A,&B,&c);temp.v=A-1;temp.weight=c;GB-1.push_back(temp);printf(%dn,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(Gsi) /存在着边disti=Gsi;elsedisti=INT_MAX;dists=0;visits=1;for(i=1;i=F;i+)u=-1;min=INT_MAX;for(j=1;j=F;j+)if(distjmin&!visitj)min=distj;u=j;if(u=-1)break;visitu=1;for(j=1;jdistu+Guj)distj=distu+Guj;3. 欧拉路径判断欧拉路径时要注意有向图无图的区别。以下是链表形式struct NODEint v,id;NODE *next;void path(int u,int id)link p;int vv,dd;while(adju)p=adju;vv=p-v;dd=p-id;adju=p-next;delete p;path(vv,dd);anstop+=id;注意这边ans是反序存结果。Sample Input26alohaarachniddoggopherrattiger3oakmapleelmSample Outputaloha.arachnid.dog.gopher.rat.tiger*#include#include#includeusing namespace std;#define maxn 1024bool cmp(string a,string b)return ab;struct NODEint v,id;NODE *next;typedef NODE *link;int ansmaxn,top,in32,out32,start;string savemaxn;link adj32;void insert(int u,int v,int id)link p=new NODE;p-v=v;p-id=id;p-next=adju;adju=p;void path(int u,int id)link p;int vv,dd;while(adju)p=adju;vv=p-v;dd=p-id;adju=p-next;delete p;path(vv,dd);anstop+=id;int check()int i,e1,e2,cnt;e1=e2=cnt=0;for(i=0;i26;i+)if(outi-ini=1)start=i;e1+;cnt+;else if(ini-outi=1)e2+;cnt+;else if(ini!=outi)return 0;if(!(cnt=2|cnt=0)return 0;if(cnt=2&e1!=1)return 0;if(cnt=0)for(i=0;iT;while(T-)cinN;for(i=0;isavei;sort(save,save+N,cmp);memset(adj,0,sizeof(adj);memset(in,0,sizeof(in);memset(out,0,sizeof(out);for(i=0;iN;i+)a=savei0-a;b=saveisavei.length()-1-a;insert(a,b,i);outa+;inb+;top=0;if(!check()cout*n;continue;elsepath(start,-1);if(top!=N+1)cout0;i-)coutsaveansi.;coutsaveans0endl;return 1;4. 最大的流1 BFS找找增广路int G402402,N,D,F,start,end,Q402,save402; /Q是村节点的队列int pre402; /村前一个节点的编号 ，邻接矩阵表示int BFS(int s,int t) int i,f,r,v; memset(pre,-1,sizeof(pre); f=r=0; Qr+=s; while(fr) v=Qf+; for(i=1;i=end;i+) if(Gvi&prei=-1) prei=v; Qr+=i; if(i=t) 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=prep) if(Gpreppd) d=Gprepp; ans+=d; for(p=t;p!=s;p=prep) Gprepp-=d; Gpprep+=d; return ans;5. 有向图的强连通分量和2-sat的判定问题#include#includeusing namespace std;#define INF 102400#define maxn 1024*2int lowmaxn*2,cnt,cnt1,stackmaxn*2,top,scmaxn*2,N,M,flag;int visitmaxn*2=0;vectorGmaxn*2;void DFS(int u)int i,len,min,v;visitu=flag;len=Gu.size();min=lowu=cnt+;stacktop+=u;for(i=0;ilowGui)min=lowGui;if(minlowu)lowu=min;elsedoscv=stack-top=cnt1;lowv=INF;while(v!=u);cnt1+;bool check()int i;cnt=cnt1=0;for(i=0;i2*N;i+)if(visiti!=flag)top=0;DFS(i);for(i=0;iN;i+)if(sci=sci+N)return false;return true;有 2N把钥匙，分成 N组，每组只能选一把钥匙有 M个门，每个门需要 X或者 Y钥匙，只要其中一把即可,选了一把后同组的令一把钥匙就永远消失。门是有顺序的，只能先开前面的才能开后面的门，求最多能开多少门？输入：N MA B 有 N行，表示 A，B钥匙一组X Y 有 M行，表示需要 X或者 Y钥匙输出：最多可以打开的门的数量。Sample Input3 60 31 24 50 10 24 14 23 52 20 0Sample Output4每把钥匙都对应一个变量A和A算法，本题采用2-sat算法，通过求强连通分量来求解。以下是代码的解释：for(i=1;i=n;i+)scanf(%d%d,&a,&b);Ga.push_back(b+N); 由于每把钥匙不能同时都用所以(AB) ABGb.push_back(a+N); AB BA (即A和B不能同 时为1）ans=0;for(i=1;i=M;i+)scanf(%d%d,&a,&b);Ga+N.push_back(b); /两把钥匙，选一就可以开门了，XY XYGb+N.push_back(a); / YXflag+;if(!check()break;elseans=i;题目意思：Farmer john要用两个中转站把所有的农场连起来，但是有些农场的牛互相恨对方，不能将这些农场连在同一个中转站，有些农场的牛是朋友必须将这些农场连在同一个农场。现在问你通过某种方案相连后，距离最远的两个农场的最小距离是多少。Sample Input4 1 112750 28546 15361 320556706 388710754 816612668 1938015788 160593 42 3Sample Output53246解题报告：标程用的算法是二分查找，给定一个答案后，用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 500int Gmaxn*2maxn*2,enmaxn*2=0,tnmaxn*2;int dismaxn2,scmaxn*2,lwmaxn*2,stackmaxn*2,top;bool visitmaxn*2;int N,A,B,low,high,sx1,sy1,sx2,sy2,DS,cnt,cnt1;inline int abs(int a)return a0?a:-a;inline void insert(int a,int b)Gaena+=b;void DFS(int u)visitu=1;stacktop+=u;lwu=cnt+;int min=lwu;int i;for(i=0;ilwGui)min=lwGui;if(minlwu)lwu=min;return;int v;doscv=stack-top=cnt1;lwv=INT_MAX;while(v!=u);cnt1+;int add_edge(int dd)int i,j,f;for(i=0;iN;i+)for(j=i+1;jdd)f+;insert(i,j+N);insert(j,i+N);if(disi1+disj1dd)f+;insert(i+N,j);insert(j+N,i);if(disi0+disj1+DSdd)f+;insert(i,j);insert(j+N,i+N);if(disi1+disj0+DSdd)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;i2*N;i+)if(!visiti)DFS(i);for(i=0;iN;i+)if(sci=sci+N)return 0;return 1;int main()int i,a,b,mid;scanf(%d%d%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=disi0;if(disi1high)high=disi1;if(disi0low)low=disi0;if(disi1low)low=disi1;for(i=0;iA;i+)scanf(%d%d,&a,&b);a-,b-;insert(a,b+N);insert(b,a+N);insert(a+N,b);insert(b+N,a);for(i=0;iB;i+)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(-1n);return 1;low*=2;high=high*2+DS;for(i=0;i2*N;i+)tni=eni;while(lowhigh)mid=(low+high)/2;memcpy(en,tn,sizeof(int)*2*N);if(add_edge(mid)&check()high=mid;elselow=mid+1;printf(%dn,high);return 1;关键部分说明：for(i=0;ib,b-a,a-binsert(b+N,a); /_b-afor(i=0;ib,b-a,b-a, a-binsert(a+N,b+N); insert(b+N,a+N);6. 求图中不含有割点（关结点）的块void dfs(int u,int father)int v,t;preu=lowu=cnt+;stacktop+=u;for(v=0;vN;v+)if(mpuv&v!=father)if(prev=-1)dfs(v,u);if(lowv=preu)dot=stack-top;savek+=t;while(t!=v);savek+=u;check(); /这个函数处理save中块的结点函数，处理完后k=0else if(lowuprev)lowu=prev;void solve()cnt=top=0;int i,ans=0;for(i=0;iN;i+)if(prei=-1)dfs(i,-1);要正确区别不含关结点的块和（有向图或无向图）的强连通分量的区别，也就是要区别双向连通性和边连通性，双向连通任何两个结点存在两条不共用结点的路径，边连通性则不共用边,可以共用结点。14352右边这个图有两个块：543231如下面的图所示：7. 图的奇环的判断,是否为二分图的判断bool color(int u,int c)int v;coru=c;for(v=0;vGu.size();v+)if(corGuv=-1)if(!color(Guv,1-c)return false;else if(corGuv=c)return false;return true;memset(cor,-1,sizeof(cor);color(0,1);8. 二分图的匹配一个GNM的图的匹配，当图的边很少时，可以采用链表来做。int myM,visitM;int path(int u)int i;for(i=0;iM;i+)if(Gui&!visiti)visiti=1;if(myi=-1|path(myi)myi=u;return 1;return 0;int macth()int i,cnt=0;memset(my,-1,sizeof(my);for(i=0;iN;i+)memset(visit,0,sizeof(visit);cnt+=path(i);return cnt;9. prim算法求最小生成树int Gmaxnmaxn=0,wtmaxn,N,stmaxn,frmaxn; void GRAPHmstV(int st,int wt) /节点编号为0到N-1 /wti 若i未加入生成树中，表示结点i到生成树中结点的最小距离。int v,w,min; /st有两个作用，初始st为-1可以作是否访问的标记，最后i-sti为所求最小for(v=0;vN;v+) /生成树的边stv=-1;frv=v;wtv=INT_MAX;st0=0; /初始0为wtN=INT_MAX;for(min=0;min!=N;)v=min;stmin=frmin;for(w=0,min=N;wN;w+) /这边注意min=N 所以要保证wtN不会越界。if(stw=-1) /w为未加入到生成树的结点if(Gvwwtw)wtw=Gvw;frw=v;if(wtwwtmin)min=w;int i;for(i=1;iN;i+) /最小生成树的边的个数为N-1printf(%d %dn,i+1,sti+1); /输出最小生成树的边10. 给有有向图最少加边使图中没有桥也就是任何两个结点都有两个不共用边的路径。Sample Input7 71 22 33 42 54 55 65 7Sample Output2#include#include#includeusing namespace std;vectorG5001;int stack5001,N,low5001,sc5001,cnt,cnt1;bool visit5001;void dfs(int father,int u) /这边多了一个father参数的作用要注意 /与有向图的的强连通分量的求法有所不同int i,len,min,v;len=Gu.size();visitu=1;stackN+=u;lowu=cnt+;min=lowu;for(i=0;ilowv)min=lowv;if(minlowu)lowu=min;elsedoscv=stack-N=cnt1;lowv=10000;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;jGa.size();j+)if(Gaj=b)break;if(jGa.size() continue;Ga.push_back(b);Gb.push_back(a);cnt=cnt1=1;dfs(0,1);vector:iterator p;memset(stack,0,sizeof(stack);for(i=1;i=N;i+)/printf(%dn,sci);for(p=Gi.begin();p!=Gi.end();p+)if(sci!=sc*p)/printf(%d %dn,sci,sc*p);stacksci+;int ans=0;for(i=1;icnt1;i+)if(stacki=1)ans+;printf(%dn,(ans+1)/2);return 1;11. 套汇问题double rate3232;void folyd()int i,j,k;for(k=0;kN;k+)for(i=0;i0)for(j=0;jrateij)rateij=rateik*ratekj;bool check()int i;for(i=0;i1)return true;return false;12. 差分系统注意差分系统只能处理x1=x2+3, x3=x4+5等（或把大于等于改成小于等于）只能是大于等于或小于等于（只能选一种，不能同时有大于等于又有小于等于）不能出大于或小于的关系。当题目给出是大于的关系时可以通过转化。x0x1+10推出x0=x1+10+1如果题目同时有大于等于又有小于等于时要把其中一个拿来转化（同时乘-1）。Sample Input4 2 11 3 102 4 202 3 3Sample Output27HintExplanation of the sample: There are 4 cows. Cows #1 and #3 must be no more than 10 units apart, cows #2 and #4 must be no more than 20 units apart, and cows #2 and #3 dislike each other and must be no fewer than 3 units apart. The best layout, in terms of coordinates on a number line, is to put cow #1 at 0, cow #2 at 7, cow #3 at 10, and cow #4 at 27.#include#define INF 999999999struct EDGEint start;int end;int more;Edge20001;int min,max,d1001,ML,MD,N;int Bellman_Ford()int i,j;bool finish;for(i=1;i=N;i+)di=INF;d1=0;for(i=0;i=N;i+)finish=true;for(j=0;jML+MD;j+)if(dEdgej.start!=INF)if(dEdgej.start+Edgej.more1;j-)if(dj!=INF)if(dj-1=INF)dj-1=dj;if(finish)break;if(!finish)return -1;if(dN=INF)return -2;elsereturn dN;inline void swap(int &a,int &b)int t=a;a=b;b=t;int main()scanf(%d%d%d,&N,&ML,&MD);int i;for(i=0;iEdgei.end)swap(Edgei.start,Edgei.end);for(;iMD+ML;i+)scanf(%d%d%d,&Edgei.end,&Edgei.start,&Edgei.more);if(Edgei.startEdgei.end)swap(Edgei.start,Edgei.end);Edgei.more=-Edgei.more;printf(%dn,Bellman_Ford();return 1;DescriptionAn integer interval a,b, a b, is a set of all consecutive integers beginning with a and ending with b. Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.InputThe first line of the input contains the number of intervals n, 1 = n = 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 = a b = 10000. They are the beginning and the end of an interval. OutputOutput the minimal number of elements in a set containing at least two different integers from each interval. Sample Input43 62 40 24 7Sample Output4include#define maxn 10001int tmpmaxn,*d=&tmp1,n,min,max;struct EDGEint start;int end;Edgemaxn;int cmp(EDGE a,EDGE b)return a.startb.start;void out()int i;for(i=min;i=max;i+)printf(%d ,di);printf(n);int Bellman_Ford()int i,j;bool finish;/sort(Edge,Edge+n,cmp);for(i=min;i=max;i+)di=0;for(i=0;in;i+)finish=1;for(j=0;jdEdgej.end)dEdgej.end=dEdgej.start+2;finish=0;for(j=min;jmax;j+)if(dj+1min;j-)if(dj-1dj-1)dj-1=dj-1;/out();if(finish)break;return dmax;int main()while(scanf(%d,&n)!=EOF)int i;min=10000000;max=-1;for(i