# 图论 Test3(20171002) 解题报告——蒟蒻 XZY

## T1

• 期望得分：100 分
• 实际得分：100 分

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define NS (10005)
#define MS (50005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;dig=0;
while(c=getchar(),!isdigit(c));
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct graph
{
void push(int a,int b)
{
}
}g1,g2;
int n,m,cnt,scc[NS],tot,ans;
bool book[NS];
stack<int> st;
void initdfs(int a)
{
book[a]=1;
if(!book[g1.to[i]])initdfs(g1.to[i]);
st.push(a);
}
void dfs(int a)
{
book[a]=1,scc[a]=cnt;
if(!book[g2.to[i]])dfs(g2.to[i]);
}
int main()
{
freopen("pop.in","r",stdin),freopen("pop.out","w",stdout);
g1.init(),g2.init(),IN(n),IN(m);
for(int i=1,a,b;i<=m;i++)IN(a),IN(b),g1.push(a,b),g2.push(b,a);
for(int i=1;i<=n;i++)if(!book[i])initdfs(i);
memset(book,0,sizeof(book));
while(!st.empty())
{
int t=st.top();st.pop();
if(!book[t])cnt++,dfs(t);
}
tot=cnt;
for(int i=1;i<=n;i++)
if(scc[i]!=scc[g1.to[j]])
tot-=book[scc[i]],book[scc[i]]=0;
if(tot>1)printf("0\n"),exit(0);
for(int i=1;i<=cnt;i++)
if(book[i])
for(int j=1;j<=n;j++)if(scc[j]==i)ans++;
printf("%d\n",ans);
return 0;
}


## T2

• 期望得分：100
• 实际得分：100

#include <bits/stdc++.h>
#pragma GCC optimize(2)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;dig=0;
while(c=getchar(),!isdigit(c));
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct edge
{
int u,v,l;
bool operator < (const edge another)const
{
return l<another.l;
}
}e[1005];
int n,m,q,f[205],s,t;
int findf(int a){return f[a]==a?a:f[a]=findf(f[a]);}
int main()
{
IN(n),IN(m);
for(int i=1;i<=m;i++)IN(e[i].u),IN(e[i].v),IN(e[i].l);
sort(e+1,e+1+m),IN(q);
while(q--)
{
IN(s),IN(t);
int ans=INT_MAX;
for(int k=1,lst;k<=m;k++)
{
for(int i=1;i<=n;i++)f[i]=i;
for(int i=k,fa[2];i<=m;i++)
{
fa[0]=findf(e[i].u),fa[1]=findf(e[i].v);
if(fa[0]==fa[1])continue;
lst=i,f[fa[0]]=fa[1];
if(findf(s)==findf(t))break;
}
if(findf(s)!=findf(t))break;
ans=min(ans,e[lst].l-e[k].l);
}
if(ans==INT_MAX)printf("-1\n");
else printf("%d\n",ans);
}
return 0;
}


## T3

• 期望得分：30
• 实际得分：100

#include <iostream>
#include <algorithm>
#include <climits>
#include <set>
#include <map>
using namespace std;
struct query{string s1,s2;int l;}Q[1000];
struct edge
{
int u,v,l;
bool operator < (const edge another)const
{
return l<another.l;
}
}e[1005];
int m,n,k,park,dis[25][25],tmp[25],x[25],y[25],dt,ans,f[25];
set<string> h;
map<string,int> h2;
bool book[25][25];
int cindf(int a){return f[a]==a?a:f[a]=cindf(f[a]);}
void dfs(int a,int fa)
{
for(int i=1;i<=n;i++)
if(book[a][i]&&i!=fa)
{
if(tmp[i]!=-1)
{
if(tmp[a]>dis[a][i])
tmp[i]=tmp[a],x[i]=x[a],y[i]=y[a];
else tmp[i]=dis[a][i],x[i]=a,y[i]=i;
}
dfs(i,a);
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>m;
for(int i=1;i<=m;i++)
cin>>Q[i].s1>>Q[i].s2>>Q[i].l,h.insert(Q[i].s1),h.insert(Q[i].s2);
for(set<string>::iterator i=h.begin();i!=h.end();i++)h2[*i]=++n;
park=h2["Park"];
for(int i=1;i<=m;i++)
{
e[i].u=h2[Q[i].s1],e[i].v=h2[Q[i].s2],e[i].l=Q[i].l;
dis[e[i].u][e[i].v]=dis[e[i].v][e[i].u]=e[i].l;
}
sort(e+1,e+1+m),cin>>k;
for(int i=1;i<=n;i++)f[i]=i;
for(int i=1;i<=m;i++)
{
if(e[i].u==park||e[i].v==park)continue;
int fa[2]={cindf(e[i].u),cindf(e[i].v)};
if(fa[0]==fa[1])continue;
ans+=e[i].l,f[fa[0]]=fa[1];
book[e[i].u][e[i].v]=book[e[i].v][e[i].u]=1;
}
dis[0][park]=dis[park][0]=INT_MAX;
for(int i=1;i<=n;i++)
if(dis[i][park]&&dis[i][park]<dis[tmp[cindf(i)]][park])
tmp[cindf(i)]=i;
for(int i=1;i<=n;i++)
if(i!=park&&cindf(i)==i)
book[tmp[i]][park]=book[park][tmp[i]]=1,ans+=dis[tmp[i]][park],dt++;
for(int i=dt+1;i<=k;i++)
{
for(int j=1;j<=n;j++)if(book[park][j])tmp[j]=-1;else tmp[j]=0;
dfs(park,0);
int mxi,mxn=0;
for(int j=1;j<=n;j++)
if(dis[j][park]&&!book[j][park])
if(dis[j][park]-tmp[j]<mxn)mxn=dis[j][park]-tmp[j],mxi=j;
if(mxn==0)break;
ans+=mxn;
book[x[mxi]][y[mxi]]=book[y[mxi]][x[mxi]]=0;
book[park][mxi]=book[mxi][park]=1;
}
cout<<"Total miles driven: "<<ans<<endl;
return 0;
}


## T4

• 期望得分：100
• 实际得分：100

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#define NS (1005)
#define MS (10005)
using namespace std;
template<typename _Tp>inline void IN(_Tp&dig)
{
char c;dig=0;
while(c=getchar(),!isdigit(c));
while(isdigit(c))dig=dig*10+c-'0',c=getchar();
}
struct graph
{
void push(int a,int b,int c,int T)
{
}
}g1,g2;
struct st
{
int u,l,tot;
bool operator < (const st another)const
{
return l>another.l;
};
};
int n,m,s,t,dis[NS],ans,minl=2e6+5;
bool book[NS];
queue<int> que;
priority_queue<st> pq;
map<int,int> MP[1005][1005];
int main()
{
freopen("travel.in","r",stdin),freopen("travel.out","w",stdout);
g1.init(),g2.init(),IN(n),IN(m);
for(int i=1,a,b,c;i<=m;i++)
IN(a),IN(b),IN(c),MP[a][b][c]++;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(MP[i][j].size())
for(map<int,int>::iterator it=MP[i][j].begin();it!=MP[i][j].end();it++)
g1.push(i,j,it->first,it->second),g2.push(j,i,it->first,it->second);
for(int i=1;i<=n;i++)dis[i]=3e6;
IN(s),IN(t),dis[t]=0,que.push(t),book[t]=1;
while(!que.empty())
{
int F=que.front();que.pop(),book[F]=0;
if(dis[g2.to[i]]>dis[F]+g2.d[i])
{
dis[g2.to[i]]=dis[F]+g2.d[i];
if(!book[g2.to[i]])que.push(g2.to[i]),book[g2.to[i]]=1;
}
}
pq.push((st){s,dis[s],1});
while(!pq.empty())
{
st F=pq.top();pq.pop();
int u=F.u,l=F.l,tot=F.tot;
if(l-minl>1)break;
if(u==t)ans+=tot,minl=min(minl,l);
int p=l-dis[u];
pq.push((st){g1.to[i],p+g1.d[i]+dis[g1.to[i]],tot*g1.tot[i]});
}
printf("%d\n",ans);
return 0;
}


### 2 条评论

~xzy 太厉害啦，ak 啦~

#### konnyakuxzy · 2017年10月16日 7:49 下午

您没发现这题比较水吗？
而且只能怪出题人啊。。。数据太水了，T3 最小生成树都过了。。。而且 T3 我一开始少输出了个空格暴零了。。。后来好 (ji) 心 (xing) 的出题人帮我复制了一下代码搞了个副本才过的。。。
我还是太弱了，还是您强%%%%%%