A: 交通运输线
时间限制: 5 Sec 内存限制: 128 MB 题目描述
战后有很多城市被严重破坏,我们需要重建城市。然而,有些建设材料只能在某些地方产生。因此,我们必须通过城市交通,来运送这些材料的城市。由于大部分道路已经在战争期间完全遭到破坏,可能有两个城市之间没有道路。当然在运输线中,更不可能存在圈。
现在,你的任务来了。给你战后的道路情况,我们想知道,两个城市之间是否存在道路,如果存在,输出这两个城市之间的最短路径长度。
输入
第一行一个整数Case(Case<=10)表示测试数据组数。
每组测试数据第一行三个整数N,M和C (2<=N<=10, 000) (0<=M<10, 000) (1<=c<=1000000)共有N个城市,现存M条边,共有C对运输需求。
接下来M行,每行三个整数A和B,D(1<=A,B<=N,A不等于B)表示从A到B有一条直接的公路,且距离为D。
最后C行,每行两个整数,S和T(1<=S,T<=N,S不等于T),即询问从S到T的最短路径长度。
输出
共Case行,否存在从S到T的路径,则输出最短路径,否则输出“Not connected”。
样例输入
样例输出
显然的,两个点在不同树上就不联通,那在同一个树上的最短路呢?
画几个图你会发现两个点间只有一条简单路径,不就是最短路了吗?
证明的话,用反证法如果存在另一条简单路径,图就不是树了。
1 #include 2 #include 3 #include 4 #include 5 #include 6 using namespace std; 7 #define N 2000005 8 queue Q; 9 int dis[N],v[N],col[N],fa[N],anc[N],ans[N];10 struct node{11 int v,c;12 };13 vector vec[N];14 vector vec_[N];15 int find(int x){16 return x==fa[x]?x:fa[x]=find(fa[x]);17 }18 void Dis(int u,int f){19 v[u]=1;20 for (int size=vec[u].size(),i=0;i
View Code B:这不是Floyd
时间限制: 1 Sec 内存限制: 128 MB 题目描述
当一个有向图给出,我们可以通过著名的Floyd算法方便的求解出其传递闭包。
但如果你给一个图G=(V,E),您能不能给一个的最小的边集合代替原边集,使得新的图与原图各个顶点的传递性不变。
输入
有多组测试数据:
第一行,包含一个整数Num,表示测试数据的个数。(1<=Num<=100)
每组测试数据,第一行一个整数N(1<=N<=200)。
接下来N行N列的一个0,1矩阵,表示相应点对之间的连接关系。第i行第j列,若值为1,则表示有一条从i到j的有向边。否则就没有。
输出
每行输出一个整数。输出至少需要多少条边,就能与原图的传递性一致。
样例输入
样例输出
简单的想法,一个强连通图里里只要个数条边(一个点不算),
然后就是玄学了,如果一条边去掉后对图的联通性没有影响就可以去掉。
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 typedef long long ll;10 typedef long double ld;11 typedef pair pr;12 const double pi=acos(-1);13 #define rep(i,a,n) for(int i=a;i<=n;i++)14 #define per(i,n,a) for(int i=n;i>=a;i--)15 #define Rep(i,u) for(int i=head[u];i;i=Next[i])16 #define clr(a) memset(a,0,sizeof(a))17 #define pb push_back18 #define mp make_pair19 #define fi first20 #define sc second21 #define pq priority_queue22 #define pqb priority_queue
, less
>23 #define pqs priority_queue
, greater
>24 #define vec vector25 ld eps=1e-9;26 ll pp=1000000007;27 ll mo(ll a,ll pp){ if(a>=0 && a
>=1,a=mo(a*a,pp))if(b&1)ans=mo(ans*a,pp);return ans;}29 void fre() { freopen("c://test//input.in", "r", stdin); freopen("c://test//output.out", "w", stdout); }30 int dx[5]={ 0,-1,1,0,0},dy[5]={ 0,0,0,-1,1};31 ll read(){ ll ans=0; char last=' ',ch=getchar();32 while(ch<'0' || ch>'9')last=ch,ch=getchar();33 while(ch>='0' && ch<='9')ans=ans*10+ch-'0',ch=getchar();34 if(last=='-')ans=-ans; return ans;35 }36 #define N 8000537 #define mem(a) memset(a,0,sizeof(a))38 int v[N],next[N],head[N],Stack[N],Ins[N],dfn[N],low[N],belong[N],map[205][205],map_[205][205],E,e,Time,top,sum[N],ans,len,l[N],r[N];39 void add(int x,int y){ v[++e]=y; next[e]=head[x]; head[x]=e; }40 void dfs(int u){41 dfn[u]=low[u]=++Time; Stack[++top]=u; Ins[u]=1;42 for (int i=head[u];i;i=next[i])43 if (dfn[v[i]]==0){44 dfs(v[i]);45 low[u]=min(low[u],low[v[i]]);46 } else if (Ins[v[i]]) low[u]=min(low[u],dfn[v[i]]);47 if (dfn[u]==low[u]){48 E++;49 while (Stack[top]!=u){50 belong[Stack[top]]=E; sum[E]++;51 Ins[Stack[top]]=0; top--;52 }53 belong[Stack[top]]=E; sum[E]++;54 Ins[Stack[top]]=0; top--;55 if (sum[E]>1) ans+=sum[E];56 }57 }58 int main()59 {60 int T=read();61 while (T--){62 int n=read(); ans=E=e=Time=top=len=0; 63 mem(v),mem(next),mem(head),mem(Stack),mem(Ins);64 mem(dfn),mem(low),mem(belong),mem(map),mem(map_),mem(sum),mem(l),mem(r);65 for (int i=1;i<=n;i++)66 for (int j=1;j<=n;j++){67 map[i][j]=read();68 if (map[i][j]) add(i,j); 69 }70 for (int i=1;i<=n;i++)71 if (dfn[i]==0) dfs(i);72 for (int i=1;i<=n;i++)73 for (int j=1;j<=n;j++)74 if (map[i][j] && belong[i]!=belong[j]){75 len++; l[len]=belong[i]; r[len]=belong[j]; map_[belong[i]][belong[j]]++;76 }77 ans+=len;78 for(int k=1;k<=E;k++) 79 for(int i=1;i<=E;i++) 80 for(int j=1;j<=E;j++)81 map_[i][j]=map_[i][j]+map_[i][k]*map_[k][j];82 for(int i=1;i<=len;i++) 83 {84 map_[l[i]][r[i]]--;85 if(map_[l[i]][r[i]]==0) map_[l[i]][r[i]]++;86 else ans--;87 }88 printf("%d\n",ans);89 }90 return 0;91 } View Code