网站续费收多少合适,创意矿泉水瓶子设计,如何编辑网站内容,央视网商城网站建设目录#xff1a;
今天知识点
加边使得无向图图变成双连通图
找出度为0的强连通分量
加边使得有向图变成强连通图
将有向图转成DAG图进行dp POJ3352#xff1a;道路建设 思路#xff1a;
POJ2553#xff1a;图的底部
思路#xff1a;
POJ1236校园网络
思路#x…目录
今天知识点
加边使得无向图图变成双连通图
找出度为0的强连通分量
加边使得有向图变成强连通图
将有向图转成DAG图进行dp POJ3352道路建设 思路
POJ2553图的底部
思路
POJ1236校园网络
思路
缩点
思路 POJ3352道路建设 由于道路要维修维修时候来回都不能走现要在各个景点间建设新道路以便维修时候也能保证任何两个景点之间可以相互到达求最少的新道路数量 任何一对景点间最多只能在它们之间有一条道路(没有重边)。道路一开始是联通的
输入 3 3 1 2 2 3 1 3 或 10 12 1 2 1 3 1 4 2 5 2 6 5 6 3 7 3 8 7 8 4 9 4 10 9 10 思路
先求解边双连通分量然后缩点然后通过加边再把新图变成双连通图。
加边原理是这样的 先统计叶节点个数为k(k1)/2就是要建的边数。因为在树中给叶节点加边一定会产生环
说一下tarjan后的操作
for(int u1;un;u)for(int ihead[u];i;ie[i].next){int ve[i].to;if(low[u]!low[v]) deg[low[u]];//遍历新图的边其实就是旧图的桥
//有重边也要记录。low[u]就是连通分量号每个连通分量中只有桥的点才有度}int leaf0;
// for(int i1;in;i){
// couti deg[i] low[i]\n;//看详情
// }for(int i1;in;i){//检查每个连通分量号的度一定不为零if(deg[i]1) leaf;//度是1就是叶子}cout(leaf1)/2\n; 首先是缩点low是连通分量号把度(无向图没有入度出度之分)统计到桥点身上很像并查集中的缩点到祖宗点身上注意我们这种缩点的过程肯定会遇到重边。此题中的重边是不能去掉的否则叶节点会统计错误
然后统计度为1就是叶子就行。 对于重边有时候必须要有时候不影响有时候也必须去重。要仔细分析
#include bits/stdc.h//无向图的桥
using namespace std;
const int maxn10005;
int n,m;
int head[maxn],cnt;
struct node{int to,next;}e[maxn*2];
int low[maxn],dfn[maxn],deg[maxn],num;//deg是度(无向图没有入度和出度之分)void add(int u,int v){ e[cnt](node){v,head[u]};head[u]cnt;}void tarjan(int u,int fa){dfn[u]low[u]num;//初始化for(int ihead[u];i;ie[i].next){int ve[i].to;if(vfa) continue;//不可以走父子边回去if(!dfn[v]){//没访问过就递归访问tarjan(v,u);low[u]min(low[u],low[v]);//low是自己或子孙能走回的最小dfn}else{//可以从非父子边回去就要获取dfn值就是该点能回到的最小dfnlow[u]min(low[u],dfn[v]);}}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(dfn,0,sizeof(dfn));memset(deg,0,sizeof(deg));cntnum0;
}int main(){while(cinnm){init();int u,v;while(m--){cinuv;add(u,v);add(v,u);}tarjan(1,0);//求边双连通分量for(int u1;un;u)for(int ihead[u];i;ie[i].next){int ve[i].to;//遍历新图的边其实就是旧图的桥if(low[u]!low[v]) deg[low[u]];
//有重边也要记录。low[u]就是连通分量号每个连通分量中只有桥的点才有度}int leaf0;
// for(int i1;in;i){
// couti deg[i] low[i]\n;//看详情
// }for(int i1;in;i){//检查每个连通分量号的度一定不为零if(deg[i]1) leaf;//度是1就是叶子}cout(leaf1)/2\n;}
}POJ2553图的底部 有向图中若v可以到的任何一个uu也可以到v则v是一个sink点图的底部是由所有sink点构成的按顺序输出所有sink点编号没有sink就输出一个空行
输:: 3 3 1 3 2 3 3 1 2 1 1 2 0
思路
你只需要输出出度为0的连通分量中的所有点编号即可。
DAG图的出度为0的节点相当于终点
for(int u1;un;u)for(int ihead[u];i;ie[i].next){//对所有边进行判断是不是连接着两个分量int ve[i].to;if(be[u]!be[v]){//有重边out[be[u]];//缩点}}
int f1;
for(int i1;in;i){if(!out[be[i]]){//输出出度为0的连通分量中的点if(f) f0;else cout ;//一个数前面有个空格couti; }
}
不同于无向图有向图的连通分量号我们用一个be数组存起来
然后对所有边进行判断是不是连接着两个分量然后对新树中的边统计出度输出出度为0的连通分量中的点
#include bits/stdc.h
using namespace std;
const int maxn5050;
bool ins[maxn];//标记是否在栈中
int n,m;
int head[maxn],be[maxn],out[maxn];//be是属于哪个连通分量out是缩点的出度
int low[maxn],dfn[maxn],num,id,cnt;
stack int s;
struct node{int to,next;}e[maxn*2];void add(int u,int v){ e[cnt](node){v,head[u]};head[u]cnt;}void tarjan(int u){dfn[u]low[u]num;//dfn访问序号low是能走回到的最早的dfnins[u]1;s.push(u);//第一次访问节点时候入栈for(int ihead[u];i;ie[i].next){int ve[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]min(low[u],low[v]);//获取孩子的最小的low值 }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){//low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是同一个连通分量的int v;do{//一定要先执行再判断vs.top();s.pop();be[v]id;//把这些弹出的点标记同一个id号(连通分量号)ins[v]0;}while(v!u);//直到是自己为止id;}
}void init(){memset(head,0,sizeof(head));memset(low,0,sizeof(low));memset(ins,0,sizeof(ins));memset(dfn,0,sizeof(dfn));memset(out,0,sizeof(out));memset(be,0,sizeof(be));cntnum0;id1;
}int main(){while((cinn)n){//点数cinm;//边数init();int u,v;while(m--){cinuv;add(u,v);}for(int i1;in;i){if(!dfn[i]) tarjan(i);//有向图}for(int u1;un;u)for(int ihead[u];i;ie[i].next){int ve[i].to;if(be[u]!be[v]){//有重边out[be[u]];//缩点}}int f1;for(int i1;in;i){if(!out[be[i]]){//输出出度为0的连通分量中的点if(f) f0;else cout ;//输出格式罢了不用在乎这里couti; }}}
} POJ1236校园网络 每所学校都有一份发学校名单。计算至少先发给多少个学校才能使软件传到所有学校(任务1)计算至少增加多少扩展才能将软件发给任意学校结果都能传到所有学校(扩展就是将新成员引入一所学校的接收者名单) 5 2 4 3 0 4 5 0 0 0 1 0 思路 任务1每一个入度为0的连通分量都必须收到一个软件计算个数。 任务2每个连通分量必须既有入度也有出度即入度为0的连通分量必须扩展一下出度为0的连通分量必须也扩展一下入度和出度对接输出max就行
DAG图中入度为0的点相当于起点
#include bits/stdc.h//有向图的强连通分量
using namespace std;
const int maxn5050;
bool ins[maxn];
int n,m,cnt;
int head[maxn],be[maxn],in[maxn],out[maxn];//be是属于哪个连通分量 in,out是每个连通分量的入度和出度
int low[maxn],dfn[maxn],num,id;
stack int s;
struct node{int to,next;}e[maxn*2];void add(int u,int v){ e[cnt](node){v,head[u]};head[u]cnt;}void tarjan(int u){dfn[u]low[u]num;//dfn访问序号low是能走回到的最早的dfnins[u]1;s.push(u);//第一次访问节点时候入栈for(int ihead[u];i;ie[i].next){int ve[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]min(low[u],low[v]);//获取孩子的最小的low值 }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){//low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是同一个连通分量的int v;id;do{//一定要先执行再判断vs.top();s.pop();be[v]id;//把这些弹出的点标记同一个id号(连通分量号)ins[v]0;}while(v!u);//直到是自己为止}
}int main(){cinn;int v;//n为学校数量for(int i1;in;i){while(cinvv)add(i,v);//表示接收i的v学校以0结尾}for(int i1;in;i){if(!dfn[i]) tarjan(i);}for(int u1;un;u)for(int ihead[u];i;ie[i].next){int ve[i].to;if(be[u]!be[v]){//有重边可以输出一下in[be[v]];out[be[u]];//统计入度和出度来缩点}}if(id1){//一共只要一个连通分量的话要特判cout1\n;cout0\n;return 0;}int ans10,ans20;//for(int i1;in;i)couti be[i]\n;for(int i1;iid;i){// couti in in[i] , out out[i]\n;if(!in[i]) ans1;if(!out[i]) ans2;}coutans1\n;coutmax(ans1,ans2)\n;
} 缩点 思路
有向图中的强连通分量中的所有权值一定要全部加上所以缩点建出新的DAG图然后转化成了每个点走一次求最大点权值和 设置dp[v]表示到v点的最大权值和。 dp[v]max(dp[u])即可也就是要先求dp[u]再求dp[v]topo排序求一边就行了。完了 if(low[u]dfn[u]){//low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是同一个连通分量的int v; do{//一定要先执行再判断vs.top();s.pop();be[v]u;//把这些弹出的点标记同一个id号(连通分量号)ins[v]0;if(uv)break;//自己不要和自己加p[u]p[v];}while(v!u);//直到是自己为止}
首先是缩点操作要把该连通分量中点的权值加给连通分量点自己(类似无向图的桥点) for (int i1;im;i)//遍历每个边{int ube[e[i].from],vbe[e[i].to];//from是起点to是终点if (u!v)//不同的分量号点间进行建边有重边也不影响topo结果{newe[tt](node){v,hh[u],u};hh[u]tt;in[v];//建新边过程相当于add功能}}
然后是给新DAG图建边以便后面topo。 完整代码
#includebits/stdc.h
using namespace std;
const int maxn1000015;
int n,m,tot,head[maxn],tt,hh[maxn],p[maxn];//p是每个点的权值,head和tot和e是原图的hh和tt和newe是新图的
int num,low[maxn],dfn[maxn],ins[maxn],be[maxn];//be是每个所属的连通分量号
int in[maxn],dp[maxn];
stackints;
struct node{int to,next,from;}e[maxn*10],newe[maxn*10];void add(int u,int v){e[tot](node){v,head[u],u};head[u]tot;}void tarjan(int u){dfn[u]low[u]num;//dfn访问序号low使能回溯到的最早的dfnins[u]1;s.push(u);//第一次访问节点时候入栈for(int ihead[u];i;ie[i].next){int ve[i].to;if(!dfn[v]){//没访问过就递归访问tarjan(v);low[u]min(low[u],low[v]);//获取孩子的最小的low值 }else if(ins[v]){//已经访问过且在栈中获取dfn号low[u]min(low[u],dfn[v]);}}if(low[u]dfn[u]){//low[u]dfn[u]时则从栈中不断弹出节点直到x出栈停止。弹出的节点就是同一个连通分量的int v; do{//一定要先执行再判断vs.top();s.pop();be[v]u;//把这些弹出的点标记同一个id号(连通分量号)ins[v]0;if(uv)break;//自己不要和自己加p[u]p[v];}while(v!u);//直到是自己为止}
}int topo()
{queue int q;int tot0;for (int i1;in;i){if(be[i]i!in[i]){q.push(i);dp[i]p[i];}}while (!q.empty()){int uq.front();q.pop();for (int ihh[u];i;inewe[i].next){int vnewe[i].to;dp[v]max(dp[v],dp[u]p[v]);//要最大的起点嘛in[v]--;if (in[v]0) q.push(v);}}int ans0;for (int i1;in;i)ansmax(ans,dp[i]);return ans;
}
int main()
{scanf(%d%d,n,m);for (int i1;in;i)scanf(%d,p[i]);//权值for (int i1;im;i){int u,v;scanf(%d%d,u,v);add(u,v);}for (int i1;in;i)if (!dfn[i]) tarjan(i);for (int i1;im;i){int ube[e[i].from],vbe[e[i].to];//from是起点to是终点if (u!v)//不同的分量号点间进行建边有重边也不影响topo结果{newe[tt](node){v,hh[u],u};hh[u]tt;in[v];//建新边过程相当于add功能}}printf(%d,topo());
}
