又回学校了，╮(╯▽╰)╭
第一题：由于城市群之间的距离是相同的特性，根据网络流想到增点，用一个新点代表一个城市群，注意判断出边和入边，我是用二维dis表示出入+SPFA
#include#include #include #include #include using namespace std;#define INF 1000000008const int maxn = 4e5+5;struct edge{ int to,co;};vector G[maxn];bool inq[maxn];int dis[maxn][2];void read(int &x){ int f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){ if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();} x*=f;}int n,m,m1,m2,s,t;void SPFA(int s){ queue Q; Q.push(s); dis[s][0] = 0; inq[s] = 1; while(!Q.empty()){ int u = Q.front(); Q.pop(); inq[u] = 0; for(int i = 0; i < (int)G[u].size(); i++){ edge &e = G[u][i]; int x = 0,y = 0; if(u>n&&e.to>n)y=1; if(u>n&&e.to<=n)x=1; if(dis[e.to][y] > dis[u][x] + e.co){ dis[e.to][y] = dis[u][x] + e.co; if(!inq[e.to])Q.push(e.to), inq[e.to] = 1; } } }}int main(){ freopen("map.in","r",stdin); freopen("map.out","w",stdout); read(n),read(m); int N = 1+n+m; for(int i = 1+n; i < N; i++){ int u, k; read(k); while(k--){ read(u); G[i].push_back((edge){u,0}); G[u].push_back((edge){i,0}); } } read(m1); while(m1--){ int u,v,w; read(u),read(v),read(w); G[u].push_back((edge){v,w}); G[v].push_back((edge){u,w}); } read(m2); while(m2--){ int u,v,w; read(u),read(v),read(w); G[u+n].push_back((edge){v+n,w}); G[v+n].push_back((edge){u+n,w}); } read(s),read(t); for(int i = 1; i <= N; i++) dis[i][0] = dis[i][1] = INF; SPFA(s); if(dis[t][0] == INF&& dis[t][1] == INF)cout<<-1<
标答是建一个出点和一个入点+dijstra
#include#include #include #include #include #include #include #include
第二题 解析见第一测最后一题，一定要注意tarjan里面弹栈
#include#include #include #include #include #include using namespace std;const int maxn = 30005;void read(int &x){ int f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){ if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();} x*=f;}int dfn[maxn],low[maxn],idx,scc[maxn],scccnt;int t[maxn],top,r[maxn];bool ins[maxn];vector G[maxn], g[maxn];void tarjan(int s){ dfn[s] = low[s] = ++idx; t[++top] = s; ins[s] = 1; for(int i = 0; i < (int)G[s].size(); i++){ int v = G[s][i]; if(!dfn[v]){ tarjan(v); low[s] = min (low[s], low[v]); } else if(ins[v])low[s] = min(low[s], dfn[v]); } if(low[s] == dfn[s]){ scccnt++; int x = low[s]; while(1){ scc[t[top]] = scccnt; ins[t[top--]] = 0; if(t[top+1] == s)break; } }} bool topsort(){ queue q; int cnt = 0; for(int i = 1; i <= scccnt; i++) if(!r[i])cnt++, q.push(i); if(cnt >= 2)return 0; while(!q.empty()){ cnt = 0; int i = q.front(); q.pop(); for(int j = 0; j < g[i].size(); j++){ int v = g[i][j]; r[v]--; if(!r[v]){ q.push(v); cnt++; } } if(cnt >= 2)return 0; } return 1;}int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); int T,n,m; read(T); while(T--){ read(n),read(m); scccnt = idx = top = 0; memset(r,0,sizeof(r)); memset(dfn,0,sizeof(dfn)); memset(low,0,sizeof(low)); memset(ins,0,sizeof(ins)); memset(scc,0,sizeof(scc)); for(int i = 1; i <= n; i++) G[i].clear(),g[i].clear(); for(int i = 1; i <= m; i++){ int u, v; read(u),read(v); G[u].push_back(v); } for(int i = 1; i <= n; i++) if(!dfn[i])tarjan(i); for(int i = 1; i <= n; i++){ int u = scc[i]; for(int j = 0; j < (int)G[i].size(); j++){ int v = scc[G[i][j]]; if(u != v){ g[u].push_back(v); r[v]++; } } } if(topsort())printf("Yes\n"); else printf("No\n"); } }
第三题 先一个裸地最小生成树，在对选择每个公司进行模拟（在新图上连边），还需要新连的边一定在原生成树的边中，正确性易见，这样复杂度从m*k变成了m*n;
#include#include #include #include #include using namespace std;#define INF 50000000000009LL const int maxn = 30005;const int maxm = 200000+5;int f[maxn], a[maxn];struct edge { int u,v,co; };edge G[maxm],N[maxm];vector K[maxn];void read(int &x){ int f=1;x=0;char s=getchar(); while(s>'9'||s<'0'){ if(s=='-')f=-1;s=getchar();} while(s<='9'&&s>='0'){x=x*10+s-'0';s=getchar();} x*=f;}int Find(int x){ return f[x] == x ? x : f[x] = Find(f[x]);}void Union(int u,int v){ int x = Find(u), y =Find(v); f[x]= y;}bool check(int u,int v){ return Find(u) == Find(v);}bool cmp(edge a, edge b){ return a.co < b.co;}int main(){ freopen("airplane.in","r",stdin); freopen("airplane.out","w",stdout); int n, m, k, tot = 0, cnt = 0; long long ans = INF; int q = 0; read(n),read(m),read(k); for(int i = 1; i <= m ;i++)read(a[i]); for(int i = 1; i <= k; i++){ int u, v, w, s; read(u),read(v),read(w),read(s); G[++tot]=(edge){u,v,w}; G[++tot]=(edge){v,u,w}; K[s].push_back(u); K[s].push_back(v); } sort(G+1, G+1+tot, cmp); for(int i = 1; i <= n; i++)f[i] = i; for(int i = 1; i <= tot; i++){ int u = G[i].u, v = G[i].v; if(!check(u, v)){ Union(u, v); N[++q] = G[i]; } if(q == n-1)break; } sort(N+1, N+1+q, cmp); for(int i = 1; i <= m; i++){ long long money = 0; int p = 0, cnt = 0; for(int j = 1; j <= n; j++)f[j] = j; for(int j = 0; j < (int)K[i].size(); j+=2){ int u = K[i][j], v = K[i][j+1]; if(!check(u, v)){ Union(u,v); cnt++; } } cnt = n - 1 - cnt; for(int j = 1; j <= q; j++){ int u = N[j].u, v = N[j].v; if(!check(u, v)){ Union(u, v); money += N[j].co; p++; } if(cnt == p)break; } ans = min(ans, (long long)money+a[i]); } cout< <