互联网网站备案,域名服务商平台,怎样注册网站,如何做条形码网站怎么搞概念
基环树就是有n个点n条边的图#xff08;比树多出现一个环#xff09;。
特殊形态的基环树 无向树(N点N边无向图) 外向树(每个点只有一条入边) 内向树(每个点只有一条出边)
以上三种树有十分优秀的性质#xff0c;就是可以直接将环作为根。就可以对每个环的子树进行单…概念
基环树就是有n个点n条边的图比树多出现一个环。
特殊形态的基环树 无向树(N点N边无向图) 外向树(每个点只有一条入边) 内向树(每个点只有一条出边)
以上三种树有十分优秀的性质就是可以直接将环作为根。就可以对每个环的子树进行单独处理最后再处理环
找环
无向图
#includeiostream
#includecstdio
#includecstring
#includealgorithm
using namespace std;
const int N5010;
struct Edge{int v,nxt;}edge[N1];
struct Line{int u,v;}line[N1];
int n,m,cnt,head[N],dfn[N],ind,fa[N],loop[N],len;
bool ban[N][N];
int t,ans[N],rec[N];
bool cmp(Line a,Line b){return a.vb.v;}
void addedge(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void getloop(int u){dfn[u]ind;for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vfa[u]) continue;if(dfn[v]){if(dfn[v]dfn[u]) continue;for(int xv;x!fa[u];xfa[x]) loop[len]x;}else{fa[v]u;getloop(v);}}
}
void dfs(int u,int f){rec[t]u;for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(vf) continue;if(ban[u][v]) continue;dfs(v,u);}
}
void getmin(){bool flag0;int i;for(i1;in;i){if(rec[i]ans[i]){flag1;break;}else if(rec[i]ans[i]) return;}if(!flag) return;for(;in;i) ans[i]rec[i];
}
int main(){memset(ans,0x7f,sizeof(ans));scanf(%d%d,n,m);for(int i1;im;i){int u,v;scanf(%d%d,u,v);line[i](Line){u,v};line[im](Line){v,u};}sort(line1,line2*m1,cmp);for(int i1;i2*m;i) addedge(line[i].u,line[i].v);if(mn-1){dfs(1,0);for(int i1;in;i) printf(%d ,rec[i]);return 0;}getloop(1);loop[len]loop[1];for(int i1;ilen;i){//枚举删除的边ban[loop[i]][loop[i1]]ban[loop[i1]][loop[i]]1;t0;dfs(1,0);getmin();ban[loop[i]][loop[i1]]ban[loop[i1]][loop[i]]0;}for(int i1;in;i) printf(%d ,ans[i]);return 0;
}有向图
#includeiostream
#includecstdio
#includealgorithm
#includecstring
#define N 1000010
#define int long long
using namespace std;
struct Edge{int v,nxt;}edge[N];
int w[N],n,ans,cnt,f[N][2],head[N],d[N],mark;
bool vis[N];
void add(int u,int v){edge[cnt].vv;edge[cnt].nxthead[u];head[u]cnt;
}
void getloop(int u){//找环vis[u]true;if(vis[d[u]]) marku;else getloop(d[u]);return;
}
void dp(int u){vis[u]true;f[u][1]w[u];f[u][0]0;for(int ihead[u];i;iedge[i].nxt){int vedge[i].v;if(v!mark){dp(v);f[u][0]max(f[v][1],f[v][0]);f[u][1]f[v][0];}else f[v][1]-2147483647/3;}return;
}
signed main(){scanf(%d,n);for(int i1;in;i){scanf(%d%d,w[i],d[i]);add(d[i],i);}for(int i1;in;i){if(vis[i]) continue;getloop(i);dp(mark);int maxnmax(f[mark][0],f[mark][1]);markd[mark];dp(mark);ansmax(maxn,max(f[mark][0],f[mark][1]));}printf(%lld,ans);
}一般问题解决方法
一般解决方法都是如果是树形dp就对环部分进行环形dp的操作。不然可以考虑断环法。
断环法 每次断开环上的一条边跑一遍答案然后取最大值。 适用于数据较小且环不会影响答案的题目 [NOIP2018 提高组] 旅行二次dp法 对于环我们可以像环形dp一样将一条边强行断开处理一遍然后强行连上再处理一遍 适用于这样子跑满足正确性的 [ZJOI2008]骑士断环复制法 对于环我们可以像环形dp一样断开环然后再复制一遍放在后面 适用于多个需要维护的 [IOI2008] Island
