Problem Description
终于有一天,王元姬用他的劫打上了最强王者。他号称,他从来不会在偶数段位停留,因为他的实力太强会跳段(这个13我给满分)。傲娇棠和翔妹觉得他的13装的都比勇哥哥好了,所以要打击他一下,就拿他最擅长的劫来出了一道题。
假设在瓦洛兰大路上有劫的影子一共n个,影子与影子之间共有m条路,路的长度为1.每两个影子之间有一个能量值,能量值为一个影子能到达另一个影子的最短路,如果不能到达,则说明这两个影子之间不存在能量值。
这时,姜天姬粗现了。他觉得这样还是太简单了。姜天姬说,我的皇子eq能切断一条路。这样请你再计算所有劫的影子的能量值之和。
对于每一条路,输出如果姜天姬切断这条路,剩余路中所有劫的影子的能量值之和。如果任意两个影子之间不存在能量值,则输出“无形装13,最为致命”.
假设在瓦洛兰大路上有劫的影子一共n个,影子与影子之间共有m条路,路的长度为1.每两个影子之间有一个能量值,能量值为一个影子能到达另一个影子的最短路,如果不能到达,则说明这两个影子之间不存在能量值。
这时,姜天姬粗现了。他觉得这样还是太简单了。姜天姬说,我的皇子eq能切断一条路。这样请你再计算所有劫的影子的能量值之和。
对于每一条路,输出如果姜天姬切断这条路,剩余路中所有劫的影子的能量值之和。如果任意两个影子之间不存在能量值,则输出“无形装13,最为致命”.
Input
多组测试用例,读到文件结束为止。
每组用例第一行有两个数,n,m,n代表劫共有n个影子,m代表共有m条路。
接下来m行有u,v两个数,表示路由第u个影子通道第v个影子。
2<=n,m<=60
每组用例第一行有两个数,n,m,n代表劫共有n个影子,m代表共有m条路。
接下来m行有u,v两个数,表示路由第u个影子通道第v个影子。
2<=n,m<=60
Output
对于每组用例,输出m行。
第i行代表如果姜天姬切断第i条边,那么劫的所有影子的能量和值是多少,如果有任意两个劫的影子的能量和不存在,输出“无形装13,最为致命”。(最为致命前面的逗号为中文逗号)
第i行代表如果姜天姬切断第i条边,那么劫的所有影子的能量和值是多少,如果有任意两个劫的影子的能量和不存在,输出“无形装13,最为致命”。(最为致命前面的逗号为中文逗号)
这题主要问题在于floyd会超时。所以必须得使用类似的bfs来写
另外有个坑点就是只要有两个点不连接就是说明答案是0
#include<cstdio> #include<cstring> int n,m,i,j,k,ans,tot,head,tail,x,y; int base[505],pre[1005],vec[1005],nb[1005]; bool vis[505]; int dis[505],team[1005]; void add(int x,int y,int z) { vec[++tot]=y; pre[tot]=base[x]; base[x]=tot; nb[tot]=z; } void bfs(int s) { memset(dis,0,sizeof(dis)); memset(vis,0,sizeof(vis)); head=0; tail=1; team[1]=s; vis[s]=1; while(head<tail) { head++; int u=team[head]; for (int now=base[u];now;now=pre[now]) if (nb[now]!=k) { int v=vec[now]; if (!vis[v]) { vis[v]=1; tail++; team[tail]=v; dis[v]=dis[u]+1; } } } } int main() { while(~scanf("%d%d",&n,&m)) { tot=0; memset(base,0,sizeof(base)); for (i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y,i); add(y,x,i); } for (k=1;k<=m;k++) { bool no=0; ans=0; for (i=1;i<=n;i++) { bfs(i); for (j=1;j<=n;j++) if (j!=i) { if (dis[j]==0) no=1; else ans+=dis[j]; } if (no) break; } if (no) printf("无形装13,最为致命 "); else printf("劫影子的所有总能量之和:%d ",ans/2); } } }