品牌网站建设帮你大蝌蚪,wordpress图片资源主题,wordpress后台重定向,如何建设网址导航网站题意#xff1a;
给定一副n(n≤3000)n(n\leq 3000)n(n≤3000)个顶点#xff0c;mmm条有向边的图#xff0c;可以在图中添加有向边#xff0c;求添加的最少边数#xff0c;使得这副图满足#xff1a;如果顶点aaa到顶点bbb有边#xff0c;顶点bbb到ccc右有边#xff0c;…题意
给定一副n(n≤3000)n(n\leq 3000)n(n≤3000)个顶点mmm条有向边的图可以在图中添加有向边求添加的最少边数使得这副图满足如果顶点aaa到顶点bbb有边顶点bbb到ccc右有边那么顶点aaa到顶点ccc也有边
Solution
考虑一条单向链按指向的方向按顺序是A,B,C,D,...A,B,C,D,...A,B,C,D,...
显然A→B,B→CA\rightarrow B,B\rightarrow CA→B,B→C需要添加一条边A→CA\rightarrow CA→C此时A→C,C→DA\rightarrow C,C\rightarrow DA→C,C→D需要添加A→DA\rightarrow DA→D。更一般的情况是在从AAA出发能到达的顶点里只有与AAA距离为1的不需要添加边只需要和其他点建边即可并查集不适合有向图O(n)O(n)O(n)的搜索可以满足要求每个顶点搜索一次总复杂度O(n2)O(n^2)O(n2)
#includeiostream
#includevector
#includecstdlib
#includenumeric
#includeunistd.h
#includequeue
#includealgorithm
#includecmath
#includecstdio
#includeset
#includemap
#includestack
#includeutility
#includecctype
#includecassert
#includethread
#includebitset
using namespace std;using lllong long;
const int N2e55,inf0x3fffffff;
const long long INF0x3fffffffffffffff,mod998244353;struct way {int to,next;
}edge[N1];
int cnt,head[N];void add(int u,int v) {edge[cnt].tov;edge[cnt].nexthead[u];head[u]cnt;
}int n,m,dis[N],vis[N];int main() {#ifdef stdjudgefreopen(in.txt,r,stdin);auto TimeFlagFirstclock();#endifstd::ios::sync_with_stdio(false);std::cin.tie(nullptr);cinnm;for(int i1;im;i) {int u,v;cinuv;add(u,v);}int tot0;queueintq;for(int i1;in;i) {for(int j1;jn;j) vis[j]false;while(!q.empty()) q.pop();q.push(i);while(!q.empty()) {int uq.front(); q.pop();vis[u]true;for(int jhead[u];j;jedge[j].next) {int vedge[j].to;if(vis[v]) continue;q.push(v);}}for(int j1;jn;j) {if(i!jvis[j]) tot;}for(int jhead[i];j;jedge[j].next) tot--;}couttotendl;#ifdef stdjudgefreopen(CON,r,stdin);std::coutstd::endl耗时:std::clock()-TimeFlagFirstmsstd::endl;std::coutstd::flush;system(pause);#endifreturn 0;
}
