题目链接：https://vjudge.net/contest/172737#overview
A题：
题目意思：第一行输入一个数n表示1-n个点，然后在输入n-1行表示在原来的基础上的最小生成树，然后再给你一个k数，表示新加k个边，然后再给你原来的边M条，然后让你算在k+m条下的新的最小生成树
思路：K。。。。。最短路算法
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <stack> #define rep(i,a,b) for(int i=a;i<(b);i++) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f using namespace std; struct nde { int x,y,len; }node[1000010]; int f[1000010]; int n,k,m; void init() { rep(i,0,n+1) f[i]=i; } bool cmp(nde a,nde b) { return a.len<b.len; } int fd(int x) { while(x!=f[x]) x=f[x]; return x; } int main() { int fi=0; while(~scanf("%d",&n)) { //cout<<n<<endl; if(fi) cout<<endl; else fi++; int a,b,v; int old=0; init(); rep(i,0,n-1) scanf("%d %d %d",&a,&b,&v),old+=v; scanf("%d",&k); ///cout<<k<<endl; int cnt=0; rep(i,0,k) scanf("%d %d %d",&node[cnt].x,&node[cnt].y,&node[cnt].len),cnt++; scanf("%d",&m); //cout<<m<<endl; rep(i,0,m) scanf("%d %d %d",&node[cnt].x,&node[cnt].y,&node[cnt].len),cnt++; sort(node,node+cnt,cmp); //rep(i,0,cnt) cout<<i<<" "<<node[i].x<<" "<<node[i].y<<" "<<node[i].len<<endl; int newcost=0; rep(i,0,cnt) { //cout<<i<<" "<<node[i].x<<" "<<node[i].y<<endl; int nx=fd(node[i].x),ny=fd(node[i].y); //cout<<nx<<" "<<ny<<endl; if(nx!=ny) { f[nx]=ny; newcost+=node[i].len; //cout<<node[i].len<<endl; } } printf("%d %d ",old,newcost); } return 0; }
B题：
判断输入的边构成的是不是一颗树
没有子环，没有环，空树也是树
代码：
#include <stdio.h> #include <string.h> #include <iostream> #include <set> #include <queue> #include <algorithm> using namespace std; int f[100005]; int c[100005]; int fd(int x) { while(f[x]!=x) { x=f[x]; } return x; } int main() { int cs=1; int a,b; while(scanf("%d %d",&a,&b)!=EOF) { if(a==0&&b==0) { printf("Case %d is a tree. ",cs); cs++; continue; } int flag=1; if(a==b) flag=0; if(a<0&&b<0) break; for(int i=1;i<=100000;i++) { f[i]=i; } memset(c,0,sizeof(c)); f[b]=a; int sum=0; if(!c[a]) { sum++; c[a]=1; } if(!c[b]) { sum++; c[b]=1; } while(scanf("%d %d",&a,&b)!=EOF) { if(a==0&&b==0) break; if(flag) { if(!c[a]) { sum++; c[a]=1; } if(!c[b]) { sum++; c[b]=1; } int aa=fd(a); int bb=fd(b); if(f[b]!=b||aa==bb) { flag=0; } else { f[b]=a; } } } if(!flag) printf("Case %d is not a tree. ",cs); else { int cnt=0; for(int i=1;i<=100000;i++) { if(f[i]!=i) { cnt++; } } if(cnt==sum-1) { printf("Case %d is a tree. ",cs); } else { printf("Case %d is not a tree. ",cs); } } cs++; } return 0; }
C题：
题目：给你一些边，判断形成多少个树和多少个点
思路：并查集
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <queue> #include <stack> #include <map> #include <string> #define de(x) cout<<#x<<"="<<x<<endl; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) const int maxn = 100010; using namespace std; int f[26]; int num[26]; int v[26]; void init() { rep(i,0,26) f[i]=i,num[i]=0,v[i]=0; } int fd(int x) { while(x!=f[x]) x=f[x]; return x; } void combine(int x,int y) { int nx=fd(x),ny=fd(y); if(nx!=ny) { f[nx]=ny; } } bool cmp(int a,int b) { return a>b; } char s[1005]; int main() { int T; scanf("%d",&T); getchar(); while(T--) { init(); while(~scanf("%s",s),s[0]!='*') combine(s[1]-'A',s[3]-'A'); scanf("%s",s); int len=strlen(s); rep(i,0,len) { if(s[i]==',') continue; v[s[i]-'A']=1; } rep(i,0,26) { int x=fd(i); if(v[x]) num[x]++; } sort(num,num+26,cmp); int treenum=0,acornnum=0; rep(i,0,26) { if(num[i]>1) treenum++; if(num[i]==1) acornnum++; if(num[i]==0) break; } printf("There are %d tree(s) and %d acorn(s). ",treenum,acornnum); } return 0; }
D题：
E题：
题目：求一个线把所有点全部链接起来的最小长度
思路：K。。。。。算法或者prim
prim就是也是求最小生成树的算法，它的做法是：求到集合的最小的点加到集合里（dis[i]>len，dis数组表示第i个点到集合的距离），而dij是求到源点最小的加到集合里（dis[vs]>G[u.se][j].se+dis[us]）
prim是每次都拿出对首的出来找下一条离集合最短的加进集合并更新，dij是每次拿对首的出来找里不在集合里且里源点最近的加进去并更新（每访问一次就是源点到这个点的第几短路）
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <stack> #include <functional> #include <vector> #include <cmath> #include <queue> #define rep(i,a,b) for(int i=a;i<b;i++) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define pii pair<int,int> #define fi first #define se second #define mp(u,v) make_pair(u,v) #define sz(a) a.size() #define pdi pair<double,int> using namespace std; int n; struct nde { double x,y; }node[105]; double ans; double dis[105]; int v[105]; void prim() { priority_queue<pdi,vector<pdi>,greater<pdi> >q; mt(v,0);fill(dis,dis+105,inf); dis[0]=0; q.push(mp(dis[0],0)); while(!q.empty()) { pdi u = q.top(); //cout<<u.se<<" "<<u.fi<<endl; q.pop(); if(v[u.se]) continue; v[u.se]=1; ans+=u.fi; rep(i,0,n) { double len=(node[u.se].x-node[i].x)*(node[u.se].x-node[i].x)+(node[u.se].y-node[i].y)*(node[u.se].y-node[i].y); len=sqrt(len); //cout<<u.se<<" "<<i<<" "<<len<<" "<<v[i]<<" "<<dis[i]<<endl; if(!v[i]&&dis[i]>len) { dis[i]=len; //ŝcout<<dis[i]<<" "<<i<<endl; q.push(mp(dis[i],i)); } } } //rep(i,0,n) cout<<dis[i]<<endl; } int main() { int T; scanf("%d",&T); int fi=0; while(T--) { if(fi) cout<<endl; else fi++; scanf("%d",&n); rep(i,0,n) scanf("%lf %lf",&node[i].x,&node[i].y); ans=0; prim(); printf("%.2f ",ans); } return 0; }
F题：
G题：
题目：输入n，m，表示n个点，m个关系，每个关系为a，b表示a要先完成b才能完成，然后要我们输出任意一种符合条件的完成顺序
思路：拓扑排序，我们把b的入度++，然后每次把入度为零的加进队列，然后把入度为零的点所对应的边删了，然后再找入度为零的点加到队列
代码：
#include<stdio.h> #include<cmath> #include<iostream> #include<string.h> #include<string> #include<stack> #include<map> #include<set> #include<vector> #include<algorithm> using namespace std; int n,m,in[105]; vector<int> G[105]; void topo() //topo模板 { vector<int> q; for(int i=1;i<=n;i++) //找到第没有入度 { if(in[i]==0) { q.push_back(i); } } for(int j=0;j<q.size();j++) //从第一个开始搜索 { int t=q[j]; for(int k=0;k<G[t].size();k++) //如果下一个的入度==0就进去 { in[G[t][k]]--; if(in[G[t][k]]==0) q.push_back(G[t][k]); } } for(int i=0;i<q.size();i++) printf("%d ",q[i]); printf(" "); } int main() { while(~scanf("%d %d",&n,&m)) { if(!n&&!m) break; memset(in,0,sizeof(in)); //memset(v,0,sizeof(v)); for(int i=0;i<n;i++) G[i].clear(); for(int i=0;i<m;i++) { int u,v; scanf("%d %d",&u,&v); G[u].push_back(v); in[v]++; } topo(); } return 0; }
H题：
题目：让你从一个点出发看看有多少个点它不能访问到
思路：dfs遍历一遍图
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <stack> #include <functional> #include <vector> #include <queue> #define rep(i,a,b) for(int i=a;i<b;i++) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define pii pair<int,int> #define fi first #define se second #define mp(u,v) make_pair(u,v) #define sz(a) a.size() using namespace std; vector<int> G[105]; vector<int> g; int n,m,x; int v[105]; int vs[105]; void dfs(int a) { rep(i,0,sz(G[a])) { int b=G[a][i]; //cout<<b<<endl; if(!vs[b]) { v[b]=1; vs[b]=1; dfs(b); } } } int main() { while(~scanf("%d",&n)) { if(n==0) break; rep(i,0,n+1) G[i].clear(); int a,b; while(~scanf("%d",&a)) { if(a==0) break; while(~scanf("%d",&b)) { if(b==0) break; G[a].push_back(b); } } scanf("%d",&m); rep(i,0,m) { scanf("%d",&x); mt(v,0); mt(vs,0); dfs(x); int ans=0; rep(i,1,n+1) { if(!v[i]) ans++; } cout<<ans; rep(i,1,n+1) if(!v[i]) cout<<" "<<i; /*rep(i,0,g.size()) { cout<<" "<<g[i]; } g.clear();*/ cout<<endl; } } return 0; }
J题：
题目：让你再原来的基础上加一个火车战，使得每个点到火车战的距离的最短距离的最大值最小
思路：
floyed求一遍任意两点的最小值，然后枚举1-n为新的火车，然后更新对应新火车站为i的情况下的，任意一个点到火车站的最短路（j到新火车i近还是j到原来的火车站近）
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <sstream> #include <stack> #include <functional> #include <vector> #include <queue> #define rep(i,a,b) for(int i=a;i<b;i++) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define pii pair<int,int> #define fi first #define se second #define mp(u,v) make_pair(u,v) #define sz(a) a.size() using namespace std; int n,m; int fire[505]; int road[505][505]; vector<pii> G[105]; int main() { int T; scanf("%d",&T); while(T--) { scanf("%d %d",&n,&m); rep(i,0,n) scanf("%d",fire+i); getchar(); int a,b,c; char buf[205]; mt(road,0x3f); rep(i,0,505) road[i][i]=0; while(fgets(buf,99,stdin)&&strlen(buf)!=1)//while(gets(buf)&&strlen(buf)) { int a,b,c; sscanf(buf,"%d %d %d",&a,&b,&c); //cout<<a<<" "<<b<<" "<<c<<endl; road[a][b]=road[b][a]=c; } rep(k,1,m+1) rep(i,1,m+1) rep(j,1,m+1) road[i][j]=min(road[i][j],road[i][k]+road[k][j]); rep(i,1,m+1)//i weixinzhandian rep(j,1,m+1) rep(k,0,n) road[i][j]=min(road[i][j],road[fire[k]][j]); int mn=road[504][503]; int ans; rep(i,1,m+1) { int mx=0; rep(j,1,m+1) { mx=max(road[i][j],mx); } if(mx<mn) { mn=mx; ans=i; } } cout<<ans<<endl;if(T) cout<<endl; } return 0; }
K题：
题目：求两点的最短路
思路：dij+优先队列优化
没有优化代码：
void dij() { v[fr]=1; rep(i,0,n) dis[i]=road[fr][i]; v[fr]=1; rep(i,0,n) { int k=-1; int mn=inf; rep(j,0,n) { if(!v[j]&&dis[j]<mn) { mn=dis[j]; k=j; } } if(k==-1) break; v[k]=1; for(int j=0;j<n;j++) { if(!v[j]) { if(dis[j]>road[k][j]+dis[k]) { dis[j]=road[k][j]+dis[k]; } //cout<<dis[j]<<endl; } } } }
优化的代码：
void dij() { priority_queue<pii,vector<pii>,greater<pii> >q; while(q.size()) q.pop(); dis[fr]=0; q.push(mp(dis[fr],fr)); while(!q.empty()) { pii u=q.top(); //cout<<u.fi<<" "<<u.se<<endl; q.pop(); if(v[u.se]) continue; v[u.se]=1; rep(j,0,sz(G[u.se])) { int vs=G[u.se][j].fi; int us=u.se; //cout<<j<<" "<<dis[j]<<" "<<road[u.se][j]+dis[u.se]<<endl; if(!v[vs]&&dis[vs]>G[u.se][j].se+dis[us]) { dis[vs]=G[u.se][j].se+dis[us]; q.push(mp(dis[vs],vs)); } } } //cout<<dis[to]<<endl; }
spfa：
一开始把dis都弄成inf，源点的弄成0，然后把点推进去，更新其它点，被更新的点如果没有在队列里，就加进去，用一个v数组标记有没有在队里，可以用来处理负边，但是负环不行
代码：
void spfa()
{
queue<int> q;
q.push(fr);
mt(dis,inf);
dis[fr]=0;
v[fr]=1;
while(!q.empty())
{
int t=q.front();
q.pop();
v[t]=0;
rep(i,0,sz(G[t]))
{
int vs=G[t][i].fi,len=G[t][i].se;
if(dis[vs]>dis[t]+len)
{
dis[vs]=dis[t]+len;
if(!v[vs])
{
q.push(vs);
v[vs]=1;
}
}
}
}
}
L题：
题目：求第k条最短路
思路：可以看下E题的思路
代码：
#include <stdio.h> #include <iostream> #include <string.h> #include <algorithm> #include <stack> #include <functional> #include <vector> #include <queue> #define rep(i,a,b) for(int i=a;i<b;i++) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f #define pii pair<int,int> #define fi first #define se second #define mp(u,v) make_pair(u,v) #define sz(a) a.size() using namespace std; int n,m,k; int fr,to,d; int v[20005]; vector<pii> G[20005]; void dij() { priority_queue<pii,vector<pii>,greater<pii> >q; while(q.size()) q.pop(); q.push(mp(0,fr)); while(!q.empty()) { pii u=q.top(); q.pop(); /*if(u.se==to) { cout<<v[to]<<" "<<u.fi<<" "<<to<<endl; }*/ v[u.se]++; if(v[to]==k) { printf("%d ",u.fi); return; } if(v[u.se]>k) continue; rep(j,0,sz(G[u.se])) { int road; int vs=G[u.se][j].se; int us=u.se; road=G[u.se][j].fi+u.fi;//u.fi就是到u.se这个点到源点的路（访问k次就是第k条最短路） q.push(mp(road,vs)); } } printf("-1 "); } int main() { int T; while(1) { scanf("%d %d",&n,&m); if(n==0&&m==0) break; rep(i,0,n+1) G[i].clear(); mt(v,0); int x,y,v; scanf("%d %d %d",&fr,&to,&k); rep(i,0,m) { scanf("%d %d %d",&x,&y,&v); G[x].push_back(mp(v,y)); } dij(); } return 0; }