[luogu3505][bzoj2088][POI2010]TEL-Teleportation【分层图】

题目大意

给出了一个图，然后让你加最多的边，让点\(1\)到\(2\)之间至少要经过5条边

---

解法

比较清楚，我们可以将这个图看作一个分层图，点\(1\)为第一层，再将\(2\)作为第五层，这样第一层和第五层直接加边就可以保证我们之间至少有\(5\)条边经过了。

那么剩下的点我们还是分成\(3\)层，其中第\(2\)层为与\(1\)直接相连的节点，第\(4\)层为直接和节点\(2\)相连的节点，剩下的节点我们就放在了第\(3\)层中，那么这样我们就做好了分层工作。

很明显最优的方案就是每一层的节点都两两相连，那么我们就先将所有的点都连起来，在减掉所有不可以的边。

什么边是不可以的呢？比如说是重复的边，或者是从点\(1\)连到到了\(2\)的边，这些边都是不可以的边。

那么我们每次只需要保证我们连接的边的两个端点是\(u,v\)是\(u<v\)就可以了。

若一个第三层的点连到某个第一层的点，则该点可以向第一层的所有点连边。若一个第三层的点连到某个第四层的点，则该点可以向所有第四层的点连边。否则的话就向节点数较多的那一层连边就好了。

ac代码（我丑陋的代码）

# include <cstdio> # include <cstring> # include <algorithm> # include <ctype.h> # include <iostream> # include <cmath> # include <map> # include <vector> # include <queue> # define LL long long # define ms(a,b) memset(a,b,sizeof(a)) # define ri (register int) # define inf (0x7f7f7f7f) # define pb push_back # define fi first # define se second # define pii pair<int,int> using namespace std; inline int gi(){int w=0,x=0;char ch=0;while(!isdigit(ch)) w|=ch=='-',ch=getchar();while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();return w?-x:x; } # define N 1000005 struct edge{int to,nt; }E[N<<1]; int cnt,n,m,s1,s2;//s1表示第2层的点数，s2表示第4层点的个数 int H[N],link[N]; void addedge(int u,int v){//加边不说E[++cnt]=(edge){v,H[u]}; H[u]=cnt; } int main(){n=gi(),m=gi();for (int i=1;i<=m;i++){int u=gi(),v=gi();addedge(u,v); addedge(v,u);}for (int e=H[1];e;e=E[e].nt) link[E[e].to]=1,s1++;//将所有与1相连的节点计算出来for (int e=H[2];e;e=E[e].nt) link[E[e].to]=2,s2++;//累计所有和2相连的节点int ans=0,s3=n-s1-s2-2,now1=s1,now2=s2;//now分别表示当前我们还有处理的与1和2相连的节点个数for (int i=3;i<=n;i++){if (link[i]==1){//如果当前节点和1相连now1--,ans+=now1;//表示当前这个节点和其他和for (int e=H[i];e;e=E[e].nt){int v=E[e].to;if (link[v]&&v>i) ans--;//减掉重复的边}}if (link[i]==2){now2--,ans+=now2;for (int e=H[i];e;e=E[e].nt){int v=E[e].to;if (link[v]&&v>i) ans--;//减掉重复的边}}if (!link[i]){s3--; ans+=s3;int fg=0,s=0;for (int e=H[i];e;e=E[e].nt){int v=E[e].to;if (link[v]) fg=link[v],s++;else if (v>i) ans--;}if (fg==1) ans+=s1-s;else if (fg==2) ans+=s2-s;else ans+=max(s1,s2);}}printf("%d\n",ans);return 0; }

转载于:https://www.cnblogs.com/chhokmah/p/10465905.html

总结

以上是生活随笔为你收集整理的[luogu3505][bzoj2088][POI2010]TEL-Teleportation【分层图】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。