Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <algorithm>
- #include <string.h>
- #include <vector>
- using namespace std;
- #define MAXV 3010
- #define MAXE 100010
- struct edge {
- int a,b;
- int w;
- edge(int pa=0, int pb=0, int pw=0) :
- a(pa), b(pb), w(pw) {}
- bool operator<(const edge& e) const {
- return this->w<e.w;
- }
- };
- int rank[MAXV];
- int rep[MAXV];
- edge ls[MAXE];
- int n,m;
- vector<edge> adj[MAXV];
- int find(int a) {
- if (a!=rep[a])
- rep[a]=find(rep[a]);
- return rep[a];
- }
- bool unio(int a, int b) {
- a=find(a), b=find(b);
- if (a==b)
- return false;
- if (rank[a]>=rank[b]) {
- rep[b]=a;
- if (rank[a]==rank[b]) rank[a]++;
- }
- else rep[a]=b;
- return true;
- }
- void kruskal() {
- memset(rank,0,sizeof(rank));
- sort(ls,ls+m);
- for (int i=0; i<n; i++)
- rep[i]=i;
- for (int i=0; i<m; i++)
- if (unio(ls[i].a, ls[i].b)) {
- adj[ls[i].a].push_back(ls[i]);
- swap(ls[i].a,ls[i].b);
- adj[ls[i].a].push_back(ls[i]);
- }
- }
- int t, _42=1;
- int maxEdge[MAXV][MAXV];
- void dfs(int u, int src) {
- for (int i=0; i<(int)adj[u].size(); i++)
- if (maxEdge[src][adj[u][i].b]==-1) {
- maxEdge[src][adj[u][i].b]=max(maxEdge[src][u],
- adj[u][i].w);
- dfs(adj[u][i].b, src);
- }
- }
- int main() {
- scanf("%d", &t);
- while (t--) {
- scanf("%d %d", &n,&m);
- for (int i=0; i<m; i++) {
- int a,b,l;
- scanf("%d %d %d", &a,&b,&l);
- ls[i] = edge(--a, --b, l);
- }
- for (int i=0; i<n; i++)
- adj[i].clear();
- kruskal();
- memset(maxEdge,-1,sizeof(maxEdge));
- for (int i=0; i<n; i++)
- maxEdge[i][i]=0;
- int q;
- scanf("%d", &q);
- printf("Case %d\n", _42++);
- for (int i=0; i<q; i++) {
- int s,d;
- scanf("%d %d", &s,&d);
- if (maxEdge[--s][--d]==-1) dfs(s,s);
- printf("%d\n", maxEdge[s][d]);
- }
- printf("\n");
- }
- return 0;
- }
Add Comment
Please, Sign In to add comment