o2o商城网站系统开发,手机关键词点击排名软件,软件ui,知更鸟wordpress中文因为知道了算法tag#xff0c;所以想到了正解#xff1a;
先给出两个性质#xff1a;
边双给边定向一定可以转为强连通图,此为最优解树给边定向后R的最小值必为0
性质2证明如下#xff1a;
设树有n个节点,
若R_min!0,
则每点出度至少为1,各点出度之和至少为n,
则至少有…因为知道了算法tag所以想到了正解
先给出两个性质
边双给边定向一定可以转为强连通图,此为最优解树给边定向后R的最小值必为0
性质2证明如下
设树有n个节点,
若R_min!0,
则每点出度至少为1,各点出度之和至少为n,
则至少有n条边,但树只有n-1条边,矛盾那么这道题只要在原图上把边双缩成点即可
问题是如何构造
要解决树的构造很简单因为树上必有一点无法到达其它节点而我们又要令R_min最大那么就令这个无法到达其它节点的点为 包含点的个数最多的边双 代表的点 把这个点当做 根节点 dfs这棵树把树上的边原图上的桥定向为 son—fa可以保证R_min根节点代表的边双包含点的个数
然后就是我想不到的了边双内部要如何构造呢
虽然我自己想了一种构造方法但是T得十分惨烈……
然后第二天我去学习了dfs树发现这个问题变得很简单
这是我最后用的构造方案
void dfs(int u){vis[u]1;for(int ihead[u];i!-1;iedge_nxt[i]){int vedge_v[i];if(edge_br[i]){add_e(edge_u[i],edge_v[i],edge_id[i]);continue;}if(!aa[edge_id[i]]) aa[edge_id[i]]u,bb[edge_id[i]]v;//加判断是为了防止将定好向的(fa[u],u)边再反向 if(!vis[v]) dfs(v);}
}为什么可行
用dfs树理解这个构造方案就是将所有树边定向向下并将所有回边定向向上由dfs树的性质知这一定可行
最后放上完整代码
#includeiostream
#includecstring
#includecstdio
#includestack
using namespace std;
const int N4e55;
int edge_u[N1],edge_v[N1],edge_id[N1],edge_nxt[N1],edge_br[N1];
int n,m,head[N],cnt,a[N],b[N],aa[N],bb[N];
int dfn[N],low[N],ind,bcc[N],Bcc,bcc_sz[N];
stackint s;
void add_edge(int u,int v,int id){edge_u[cnt]u;edge_v[cnt]v;edge_id[cnt]id;edge_nxt[cnt]head[u];head[u]cnt;
}
void tarjan(int u,int fa){dfn[u]low[u]ind;s.push(u);for(int ihead[u];i!-1;iedge_nxt[i]){int vedge_v[i];if(!dfn[v]){tarjan(v,u);low[u]min(low[u],low[v]);if(low[v]dfn[u]){edge_br[i]1;edge_br[i^1]1;Bcc;int k;do{ks.top();s.pop();bcc[k]Bcc;bcc_sz[Bcc];}while(k!v);}}else{if(dfn[v]dfn[u]v!fa)low[u]min(low[u],dfn[v]);}}//勿忘考虑u为根的情况: if(!fa){Bcc;while(!s.empty()){bcc[s.top()]Bcc;bcc_sz[Bcc];s.pop();}}
}
int e_u[N1],e_v[N1],e_id[N1],e_nxt[N1];
int hd[N],ct;
void add_e(int u,int v,int id){e_u[ct]u;e_v[ct]v;e_id[ct]id;e_nxt[ct]hd[bcc[u]];//highlighthd[bcc[u]]ct;//highlight
}
int num,maxn0;
bool vis_bcc[N],vis[N];
void dfs(int u){vis[u]1;for(int ihead[u];i!-1;iedge_nxt[i]){int vedge_v[i];if(edge_br[i]){add_e(edge_u[i],edge_v[i],edge_id[i]);continue;}if(!aa[edge_id[i]]) aa[edge_id[i]]u,bb[edge_id[i]]v;//加判断是为了防止将定好向的(fa[u],u)边再反向 if(!vis[v]) dfs(v);}
}
void dfs2(int u,int fa){for(int ihd[u];i!-1;ie_nxt[i]){int vbcc[e_v[i]];if(vfa) continue;aa[e_id[i]]e_v[i],bb[e_id[i]]e_u[i];dfs2(v,u);}
}
int main(){memset(head,-1,sizeof(head));memset(hd,-1,sizeof(hd));scanf(%d%d,n,m);for(int i1;im;i){scanf(%d%d,a[i],b[i]);add_edge(a[i],b[i],i);add_edge(b[i],a[i],i);}for(int i1;in;i)if(!dfn[i]) tarjan(i,0);for(int i1;in;i){if(!vis_bcc[bcc[i]]){dfs(i);vis_bcc[bcc[i]]1;if(bcc_sz[bcc[i]]maxn){maxnbcc_sz[bcc[i]];numbcc[i];}}}dfs2(num,0);printf(%d\n,maxn);for(int i1;im;i){if(aa[i]bb[i]) printf(%d %d\n,aa[i],bb[i]);else printf(%d %d\n,a[i],b[i]);}return 0;
}
