https://www.byvoid.com/blog/scc-tarjan/
https://www.byvoid.com/blog/biconnect/
A.
d.各学校之间有单向的网络，每个学校得到一套软件后，可以通过单向网络向周边的学校传输，
问题1：初始至少需要向多少个学校发放软件，使得网络内所有的学校最终都能得到软件。
问题2：至少需要添加几条传输线路(边)，使任意向一个学校发放软件后，经过若干次传送，网络内所有的学校最终都能得到软件。
s.
首先找强连通分量，然后看强连通分量的入度为0点的总数，出度为0点的总数。
第一问为入度为0的强连通分量的个数。
第二问为入度为0的个数和出度为0的个数中大的。（将这个图的所有子树找出来，然后将一棵子树的叶子结点（出度为0）连到另外一棵子树的根结点上（入度为0），这样将所有的叶子结点和根节点全部消掉之后，就可以得到一整个强连通分量，看最少多少条边，这样就是看叶子结点和根节点哪个多，即出度为0和入度为0哪个多。证明？）
c.Tarjan
/* Tarjan算法 复杂度O(N+M) */ #include<iostream> #include<stdio.h> #include<string.h> using namespace std; const int MAXN=110;//点数 const int MAXM=10100;//边数 struct Edge{ int to,next; }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc int Index,top; int scc;//强连通分量的个数 bool Instack[MAXN]; int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc //num数组不一定需要，结合实际情况 void addedge(int u,int v){ edge[tot].to=v; edge[tot].next=head[u]; head[u]=tot++; } void Tarjan(int u){ int v; Low[u]=DFN[u]=++Index; Stack[top++]=u; Instack[u]=true; for(int i=head[u];i!=-1;i=edge[i].next){ v=edge[i].to; if(!DFN[v]){ Tarjan(v); if(Low[u]>Low[v])Low[u]=Low[v]; } else if(Instack[v]&&Low[u]>DFN[v]) Low[u]=DFN[v]; } if(Low[u]==DFN[u]){ scc++; do{ v=Stack[--top]; Instack[v]=false; Belong[v]=scc; num[scc]++; } while(v!=u); } } void solve(int N){ memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(num,0,sizeof(num)); Index=scc=top=0; for(int i=1;i<=N;i++) if(!DFN[i]) Tarjan(i); } void init(){ tot=0; memset(head,-1,sizeof(head)); } int main(){ int N; int v; int indegree[MAXN],outdegree[MAXN];//强连通分量的入度，强连通分量的出度 int in0,out0;//入度为0的强连通分量个数，出度为0的... while(~scanf("%d",&N)){ init(); memset(indegree,0,sizeof(indegree)); memset(outdegree,0,sizeof(outdegree)); in0=out0=0; for(int u=1;u<=N;++u){ while(scanf("%d",&v)){ if(v==0)break; addedge(u,v); } } solve(N); if(scc==1)printf("1 0 ");//只有一个强连通 分量 else{ //枚举所有的边，统计强连通分量的入度、出度 for(int i=1;i<=N;++i){ for(int j=head[i];j!=-1;j=edge[j].next){ if(Belong[i]!=Belong[edge[j].to]){ ++indegree[Belong[edge[j].to]]; ++outdegree[Belong[i]]; } } } //强连通分量的入度为0的个数，出度为0的个数 for(int i=1;i<=scc;++i){ if(indegree[i]==0)++in0; if(outdegree[i]==0)++out0; } if(in0>out0)printf("%d %d ",in0,in0); else printf("%d %d ",in0,out0); } } return 0; }
B.
d.求割点数目
c.这里输入用了strtok的技巧
#include <stdio.h> #include <algorithm> #include <iostream> #include <string.h> using namespace std; /* * 求 无向图的割点和桥 * 可以找出割点和桥，求删掉每个点后增加的连通块。 * 需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重 */ const int MAXN = 10010; const int MAXM = 100010; struct Edge { int to,next; bool cut;//是否为桥的标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN]; int Index,top; bool Instack[MAXN]; bool cut[MAXN]; int add_block[MAXN];//删除一个点后增加的连通块 int bridge; void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son = 0; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !DFN[v] ) { son++; Tarjan(v,u); if(Low[u] > Low[v])Low[u] = Low[v]; //桥 //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。 if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } //割点 //一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边， //即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v) if(u != pre && Low[v] >= DFN[u])//不是树根 { cut[u] = true; add_block[u]++; } } else if( Low[u] > DFN[v]) Low[u] = DFN[v]; } //树根，分支数大于1 if(u == pre && son > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; } void solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0; bridge = 0; for(int i = 1;i <= N;i++) if(!DFN[i]) Tarjan(i,i); int ans = 0; for(int i = 1;i <= N;i++) if(cut[i]) ans++; printf("%d ",ans); } void init() { tot = 0; memset(head,-1,sizeof(head)); } int g[110][110]; char buf[1010]; int main() { int n; while(scanf("%d",&n)==1 && n) { gets(buf); memset(g,0,sizeof(g)); while(gets(buf)) { if(strcmp(buf,"0")==0)break; char *p = strtok(buf," "); int u; sscanf(p,"%d",&u); p = strtok(NULL," "); int v; while(p) { sscanf(p,"%d",&v); p = strtok(NULL," "); g[u][v]=g[v][u]=1; } } init(); for(int i = 1;i <= n;i++) for(int j = i+1;j <= n;j++) if(g[i][j]) { addedge(i,j); addedge(j,i); } solve(n); } return 0; }
C.
d.求桥的数目，并按顺序输出桥
c.
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <map> #include <vector> using namespace std; /* * 求 无向图的割点和桥 * 可以找出割点和桥，求删掉每个点后增加的连通块。 * 需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重 */ const int MAXN = 10010; const int MAXM = 100010; struct Edge { int to,next; bool cut;//是否为桥的标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN]; int Index,top; bool Instack[MAXN]; bool cut[MAXN]; int add_block[MAXN];//删除一个点后增加的连通块 int bridge; void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son = 0; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !DFN[v] ) { son++; Tarjan(v,u); if(Low[u] > Low[v])Low[u] = Low[v]; //桥 //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。 if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } //割点 //一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边， //即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v) if(u != pre && Low[v] >= DFN[u])//不是树根 { cut[u] = true; add_block[u]++; } } else if( Low[u] > DFN[v]) Low[u] = DFN[v]; } //树根，分支数大于1 if(u == pre && son > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; } void solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0; bridge = 0; for(int i = 1;i <= N;i++) if( !DFN[i] ) Tarjan(i,i); printf("%d critical links ",bridge); vector<pair<int,int> >ans; for(int u = 1;u <= N;u++) for(int i = head[u];i != -1;i = edge[i].next) if(edge[i].cut && edge[i].to > u) { ans.push_back(make_pair(u,edge[i].to)); } sort(ans.begin(),ans.end()); //按顺序输出桥 for(int i = 0;i < ans.size();i++) printf("%d - %d ",ans[i].first-1,ans[i].second-1); printf(" "); } void init() { tot = 0; memset(head,-1,sizeof(head)); } //处理重边 map<int,int>mapit; inline bool isHash(int u,int v) { if(mapit[u*MAXN+v])return true; if(mapit[v*MAXN+u])return true; mapit[u*MAXN+v] = mapit[v*MAXN+u] = 1; return false; } int main() { int n; while(scanf("%d",&n) == 1) { init(); int u; int k; int v; //mapit.clear(); for(int i = 1;i <= n;i++) { scanf("%d (%d)",&u,&k); u++; //这样加边，要保证正边和反边是相邻的，建无向图 while(k--) { scanf("%d",&v); v++; if(v <= u)continue; //if(isHash(u,v))continue; addedge(u,v); addedge(v,u); } } solve(n); } return 0; }
D.
这题是给了一个连通图。
问再加入边的过程中，桥的个数。
先对原图进行双连通分支缩点。可以形成一颗树。
这颗树的边都是桥。
然后加入边以后，查询LCA，LCA上的桥都减掉。
标记边为桥不方便，直接标记桥的终点就可以了。
具体看代码吧！
很好的题目
很好的题目
#include <stdio.h> #include <iostream> #include <algorithm> #include <string.h> #include <queue> #include <vector> using namespace std; const int MAXN = 100010; const int MAXM = 400010; struct Edge { int to,next; bool cut; }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block int Index,top; int block; bool Instack[MAXN]; int bridge; void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if( v == pre )continue; if( !DFN[v] ) { Tarjan(v,u); if(Low[u] > Low[v])Low[u] = Low[v]; if(Low[v] > Low[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } } else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = block; } while( v != u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } vector<int>vec[MAXN]; int father[MAXN]; int dep[MAXN]; int a[MAXN]; void lca_bfs(int root) { memset(dep,-1,sizeof(dep)); dep[root] = 0; a[root] = 0;//桥的标记，标记桥的一个点 father[root] = -1; queue<int>q; q.push(root); while(!q.empty()) { int tmp = q.front(); q.pop(); for(int i = 0;i < vec[tmp].size();i++) { int v = vec[tmp][i]; if(dep[v]!=-1)continue; dep[v] = dep[tmp]+1; a[v] = 1; father[v] = tmp; q.push(v); } } } int ans; void lca(int u,int v) { if(dep[u]>dep[v])swap(u,v); while(dep[u]<dep[v]) { if(a[v]) { ans--; a[v] = 0; } v = father[v]; } while(u != v) { if(a[u]) { ans--; a[u] = 0; } if(a[v]) { ans--; a[v] = 0; } u = father[u]; v = father[v]; } } void solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = 0; Tarjan(1,1); for(int i = 1;i <= block;i++) vec[i].clear(); for(int u = 1;u <= N;u++) for(int i = head[u];i != -1;i = edge[i].next) if(edge[i].cut) { int v = edge[i].to; vec[Belong[u]].push_back(Belong[v]); vec[Belong[v]].push_back(Belong[u]); } lca_bfs(1); ans = block - 1; int Q; int u,v; scanf("%d",&Q); while(Q--) { scanf("%d%d",&u,&v); lca(Belong[u],Belong[v]); printf("%d ",ans); } printf(" "); } int main() { int n,m; int u,v; int iCase = 0; while(scanf("%d%d",&n,&m)==2) { iCase++; if(n==0 && m == 0)break; init(); while(m--) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } printf("Case %d: ",iCase); solve(n); } return 0; }
E.
就是给了一个连通图，问加多少条边可以变成边双连通。
去掉桥，其余的连通分支就是边双连通分支了。一个有桥的连通图要变成边双连通图的话，把双连通子图收缩为一个点，形成一颗树。需要加的边为(leaf+1)/2 (leaf为叶子结点个数)
POJ 3177 给定一个连通的无向图G，至少要添加几条边，才能使其变为双连通图。
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <map> using namespace std; const int MAXN = 5010;//点数 const int MAXM = 20010;//边数，因为是无向图，所以这个值要*2 struct Edge { int to,next; bool cut;//是否是桥标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block int Index,top; int block;//边双连通块数 bool Instack[MAXN]; int bridge;//桥的数目 void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre)continue; if( !DFN[v] ) { Tarjan(v,u); if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } } else if( Instack[v] && Low[u] > DFN[v] ) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = block; } while( v!=u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } int du[MAXN];//缩点后形成树，每个点的度数 void solve(int n) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = 0; Tarjan(1,0); int ans = 0; memset(du,0,sizeof(du)); for(int i = 1;i <= n;i++) for(int j = head[i];j != -1;j = edge[j].next) if(edge[j].cut) du[Belong[i]]++; for(int i = 1;i <= block;i++) if(du[i]==1) ans++; //找叶子结点的个数ans,构造边双连通图需要加边(ans+1)/2 printf("%d ",(ans+1)/2); } int main() { int n,m; int u,v; while(scanf("%d%d",&n,&m)==2) { init(); while(m--) { scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); } solve(n); } return 0; }
F.
问加一条边，最少可以剩下几个桥。
先双连通分量缩点，形成一颗树，然后求树的直径，就是减少的桥。
本题要处理重边的情况。
如果本来就两条重边，不能算是桥。
还会爆栈，只能C++交，手动加栈了
#pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <map> #include <vector> using namespace std; const int MAXN = 200010;//点数 const int MAXM = 2000010;//边数，因为是无向图，所以这个值要*2 struct Edge { int to,next; bool cut;//是否是桥标记 bool cong; }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~block int Index,top; int block;//边双连通块数 bool Instack[MAXN]; int bridge;//桥的数目 void addedge(int u,int v,bool pp) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut=false; edge[tot].cong = pp; head[u] = tot++; } void Tarjan(int u,int pre,bool ff) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre && (!ff))continue; if( !DFN[v] ) { Tarjan(v,u,edge[i].cong); if( Low[u] > Low[v] )Low[u] = Low[v]; if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } } else if( Instack[v] && Low[u] > DFN[v] ) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { block++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = block; } while( v!=u ); } } void init() { tot = 0; memset(head,-1,sizeof(head)); } int du[MAXN];//缩点后形成树，每个点的度数 vector<int>vec[MAXN]; int dep[MAXN]; void dfs(int u) { for(int i = 0;i < vec[u].size();i++) { int v = vec[u][i]; if(dep[v]!=-1)continue; dep[v]=dep[u]+1; dfs(v); } } void solve(int n) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); Index = top = block = 0; Tarjan(1,0,false); for(int i = 1;i <= block;i++) vec[i].clear(); for(int i = 1;i <= n;i++) for(int j = head[i];j != -1;j = edge[j].next) if(edge[j].cut) { vec[Belong[i]].push_back(Belong[edge[j].to]); } memset(dep,-1,sizeof(dep)); dep[1]=0; dfs(1); int k = 1; for(int i = 1;i <= block;i++) if(dep[i]>dep[k]) k = i; memset(dep,-1,sizeof(dep)); dep[k]=0; dfs(k); int ans = 0; for(int i = 1;i <= block;i++) ans = max(ans,dep[i]); printf("%d ",block-1-ans); } struct NN { int u,v; }node[MAXM]; bool cmp(NN a,NN b) { if(a.u != b.u)return a.u<b.u; else return a.v<b.v; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,m; int u,v; while(scanf("%d%d",&n,&m)==2) { if(n==0 && m==0)break; init(); for(int i = 0;i < m;i++) { scanf("%d%d",&u,&v); if(u==v)continue; if(u>v)swap(u,v); node[i].u = u; node[i].v = v; } sort(node,node+m,cmp); for(int i = 0;i < m;i++) { if(i == 0 || (node[i].u!=node[i-1].u || node[i].v != node[i-1].v)) { if(i < m-1 && (node[i].u==node[i+1].u && node[i].v == node[i+1].v)) { addedge(node[i].u,node[i].v,true); addedge(node[i].v,node[i].u,true); } else { addedge(node[i].u,node[i].v,false); addedge(node[i].v,node[i].u,false); } } } solve(n); } return 0; }
G.
不太懂，最后应该也不是找点最少的强连通分量，好像全都试了一遍。
求最多可以加多少边，使得最新的图不是强连通图
最终情况一定是再加一条边，整张图就是强连通的了，那么我们可以把图看成2部分x和y，x和y都是完全图，然后x每个点到y每个点都有边，但是y到x没有边，如果有肯定是强连通了，设x中有a个点，y中有b个点 则 a + b = n
则边数就是 a * (a - 1) + b * (b - 1) + a * b - m，化简得到：n * n - a * b - n - m;
如何让这个值大那就是如何选取x和y的问题了，显然a和b差距越大越好，那么就可以通过tarajan来找出一个包含点最少的强连通分量来当x，其他的强连通分量作为y，这样就很容易了
Tarjan 缩点。
/* * Author:kuangbin * 1004.cpp */ #include <stdio.h> #include <algorithm> #include <string.h> #include <iostream> #include <map> #include <vector> #include <queue> #include <set> #include <string> #include <math.h> using namespace std; /* * Tarjan算法 * 复杂度O(N+M) */ const int MAXN = 100010;//点数 const int MAXM = 100010;//边数 struct Edge { int to,next; }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc int Index,top; int scc;//强连通分量的个数 bool Instack[MAXN]; int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc //num数组不一定需要，结合实际情况 void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if( !DFN[v] ) { Tarjan(v); if( Low[u] > Low[v] )Low[u] = Low[v]; } else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; } while( v != u); } } void solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(num,0,sizeof(num)); Index = scc = top = 0; for(int i = 1;i <= N;i++) if(!DFN[i]) Tarjan(i); } void init() { tot = 0; memset(head,-1,sizeof(head)); } int in[MAXN],out[MAXN]; int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int T; scanf("%d",&T); int iCase = 0; int n,m; int u,v; while(T--) { iCase++; init(); scanf("%d%d",&n,&m); for(int i = 0;i < m;i++) { scanf("%d%d",&u,&v); addedge(u,v); } solve(n); if(scc == 1) { printf("Case %d: -1 ",iCase); continue; } for(int i = 1;i <= scc;i++) { in[i] = 0; out[i] = 0; } for(int u = 1;u <= n;u++) for(int i = head[u];i != -1;i = edge[i].next) { int v = edge[i].to; if(Belong[u]==Belong[v])continue; out[Belong[u]]++; in[Belong[v]]++; } long long sss = (long long)n*(n-1) - m; long long ans = 0; for(int i = 1;i <= scc;i++) { if(in[i]==0 || out[i] == 0) ans = max(ans,sss - (long long)num[i]*(n-num[i])); } printf("Case %d: %d ",iCase,ans); } return 0; }
H.
比较难想的题。
主要构图转化的思路很神奇，我看了题解才会的，T_T
首先n,m个点做一次二分匹配，得到匹配数最大为res. 相当于右边有m-res个点没有匹配，左边有n-res个点没有匹配。
所以在左加m-res个点，和右边所有相连。
在右边加n-res个点，个左边所有相连。
然后做n+m-res，n+m-res个点的二分匹配。（ps：其实不用再二分匹配了，手工添加剩下的就行，时间会快1s）
匹配数肯定是n+m-res;
主要是得到匹配的情况。
对于左边的点i. 把i相匹配的在右边的点，向其余和i相连的点连一有向边。
然后做强连通缩点。
如果边u-v. v和u匹配的点在一个连通分支，说明可以交换，可以u->v组合，不影响最大匹配数
/* *********************************************** Author :kuangbin Created Time :2013/8/15 23:20:43 File Name :F:2013ACM练习2013多校81010.cpp ************************************************ */ #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int MAXN = 1010; int uN,vN; int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u) { for(int v = 1; v <= vN;v++) if(g[u][v] && !used[v]) { used[v] = true; if(linker[v] == -1 || dfs(linker[v])) { linker[v] = u; return true; } } return false; } int hungary() { int res = 0; memset(linker,-1,sizeof(linker)); for(int u = 1; u <= uN;u++) { memset(used,false,sizeof(used)); if(dfs(u))res++; } return res; } int lx[MAXN]; const int MAXM = 500100;//边数 struct Edge { int to,next; }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN],Belong[MAXN];//Belong数组的值是1~scc int Index,top; int scc;//强连通分量的个数 bool Instack[MAXN]; int num[MAXN];//各个强连通分量包含点的个数，数组编号1~scc //num数组不一定需要，结合实际情况 void addedge(int u,int v) { edge[tot].to = v;edge[tot].next = head[u];head[u] = tot++; } void Tarjan(int u) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if( !DFN[v] ) { Tarjan(v); if( Low[u] > Low[v] )Low[u] = Low[v]; } else if(Instack[v] && Low[u] > DFN[v]) Low[u] = DFN[v]; } if(Low[u] == DFN[u]) { scc++; do { v = Stack[--top]; Instack[v] = false; Belong[v] = scc; num[scc]++; } while( v != u); } } void solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(num,0,sizeof(num)); Index = scc = top = 0; for(int i = 1;i <= N;i++) if(!DFN[i]) Tarjan(i); } void init() { tot = 0; memset(head,-1,sizeof(head)); } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,m; int k; int T; scanf("%d",&T); int iCase = 0; while(T--) { iCase++; scanf("%d%d",&n,&m); memset(g,0,sizeof(g)); int v; for(int i = 1;i <= n;i++) { scanf("%d",&k); while(k--) { scanf("%d",&v); g[i][v] = 1; } } uN = n; vN = m; int res = hungary(); uN = vN = n + m - res; for(int i = n+1;i <= uN;i++) for(int j = 1;j <= vN;j++) g[i][j] = 1; for(int i = 1;i <= uN;i++) for(int j = m+1;j <= vN;j++) g[i][j] = 1; hungary(); memset(lx,-1,sizeof(lx)); for(int i = 1;i <= vN;i++) if(linker[i] != -1) lx[linker[i]] = i; init(); for(int i = 1;i <= uN;i++) for(int j = 1;j <= vN;j++) if(g[i][j] && j != lx[i]) addedge(lx[i],j); solve(vN); printf("Case #%d: ",iCase); vector<int>ans; for(int i = 1;i <= n;i++) { ans.clear(); for(int j = 1; j <= m;j++) if(g[i][j] && Belong[j] == Belong[lx[i]]) ans.push_back(j); int sz = ans.size(); printf("%d",sz); for(int i = 0;i < sz;i++) printf(" %d",ans[i]); printf(" "); } } return 0; }
I.
这题的意思就是求出所有的桥，然后输出桥的权值的最小值。
但是坑点比较多。
如果一开始是不连通的，输出0.
图有重边，需要处理。
还有如果取到的最小值是0的话，要输出1，表示要派一个人过去。
/* *********************************************** Author :kuangbin Created Time :2013/9/15 星期日 12:11:49 File Name :2013杭州网络赛1001.cpp ************************************************ */ #pragma comment(linker, "/STACK:1024000000,1024000000") #include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <vector> #include <queue> #include <set> #include <map> #include <string> #include <math.h> #include <stdlib.h> #include <time.h> using namespace std; const int INF = 0x3f3f3f3f; /* * 求 无向图的割点和桥 * 可以找出割点和桥，求删掉每个点后增加的连通块。 * 需要注意重边的处理，可以先用矩阵存，再转邻接表，或者进行判重 */ const int MAXN = 10010; const int MAXM = 2000010; struct Edge { int to,next; int w; bool cut;//是否为桥的标记 }edge[MAXM]; int head[MAXN],tot; int Low[MAXN],DFN[MAXN],Stack[MAXN]; int Index,top; bool Instack[MAXN]; bool cut[MAXN]; int add_block[MAXN];//删除一个点后增加的连通块 int bridge; void addedge(int u,int v,int w) { edge[tot].to = v;edge[tot].next = head[u];edge[tot].cut = false; edge[tot].w = w; head[u] = tot++; } void Tarjan(int u,int pre) { int v; Low[u] = DFN[u] = ++Index; Stack[top++] = u; Instack[u] = true; int son = 0; int pre_num = 0; for(int i = head[u];i != -1;i = edge[i].next) { v = edge[i].to; if(v == pre && pre_num == 0) { pre_num++; continue; } if( !DFN[v] ) { son++; Tarjan(v,u); if(Low[u] > Low[v])Low[u] = Low[v]; //桥 //一条无向边(u,v)是桥，当且仅当(u,v)为树枝边，且满足DFS(u)<Low(v)。 if(Low[v] > DFN[u]) { bridge++; edge[i].cut = true; edge[i^1].cut = true; } //割点 //一个顶点u是割点，当且仅当满足(1)或(2) (1) u为树根，且u有多于一个子树。 //(2) u不为树根，且满足存在(u,v)为树枝边(或称父子边， //即u为v在搜索树中的父亲)，使得DFS(u)<=Low(v) if(u != pre && Low[v] >= DFN[u])//不是树根 { cut[u] = true; add_block[u]++; } } else if( Low[u] > DFN[v]) Low[u] = DFN[v]; } //树根，分支数大于1 if(u == pre && son > 1)cut[u] = true; if(u == pre)add_block[u] = son - 1; Instack[u] = false; top--; } int solve(int N) { memset(DFN,0,sizeof(DFN)); memset(Instack,false,sizeof(Instack)); memset(add_block,0,sizeof(add_block)); memset(cut,false,sizeof(cut)); Index = top = 0; bridge = 0; for(int i = 1;i <= N;i++) if( !DFN[i] ) Tarjan(i,i); int ret = INF; for(int u = 1; u <= N;u++) for(int i = head[u]; i != -1;i = edge[i].next) if(edge[i].cut) ret = min(ret,edge[i].w); if(ret == INF)ret = -1; if(ret == 0)ret++; return ret; } int F[MAXN]; int find(int x) { if(F[x] == -1)return x; else return F[x] = find(F[x]); } void init() { memset(F,-1,sizeof(F)); tot = 0; memset(head,-1,sizeof(head)); } void bing(int u,int v) { int t1 = find(u); int t2 = find(v); if(t1 != t2)F[t1] = t2; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); int n,m; while(scanf("%d%d",&n,&m) == 2) { if(n == 0 && m == 0)break; int u,v,w; init(); while(m--) { scanf("%d%d%d",&u,&v,&w); if(u == v)continue; addedge(u,v,w); addedge(v,u,w); bing(u,v); } bool flag = true; for(int i = 1; i <= n;i++) if(find(i) != find(1)) flag = false; if(!flag) { printf("0 "); continue; } printf("%d ",solve(n)); } return 0; }