20171012 图论 test3
考试策略
看完题目，T1 和 T2 是做过的题，T4 有 60 分是最短路计数，但是好像改一改就可以过？T3 暂时没有思路。于是我就先快速打了 T1 和 T2，然后想出了 T4 的解法，写了 T4，再后来发现 T3 有 30 分是裸的最小生成树，再想了想写了个骗分一般的程序…… 结果 A 了？？（然而是因为数据水）
T1
期望得分：100 实际得分：100
题目描述：poj2186
题目分析：tarjan 缩点，然后如果入度为 0 的点只有一个，输出那个强连通分量的大小，否则输出 0.
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
const int N=10005,M=50005;
int n,m,tot,now,cn,top;
int h[N],to[M],ne[M],du[N],pos[N],low[N],dnf[N],ins[N],s[N],js[N];
void add(int x,int y){to[++tot]=y,ne[tot]=h[x],h[x]=tot;}
void dfs(int x){
++now;dnf[x]=low[x]=now;
s[++top]=x,ins[x]=1;
for(int i=h[x];i!=-1;i=ne[i])
if(!dnf[to[i]])dfs(to[i]),low[x]=min(low[x],low[to[i]]);
else if(ins[to[i]])low[x]=min(low[x],dnf[to[i]]);
if(low[x]==dnf[x]){
++cn;int kl;
do{
kl=s[top],--top,pos[kl]=cn,ins[kl]=0,++js[cn];
}while(kl!=x);
}
}
int main()
{
freopen("pop.in","r",stdin);
freopen("pop.out","w",stdout);
int i,x,y,bj=0,ans=0;
n=read(),m=read();
for(i=1;i<=n;++i)h[i]=-1;
for(i=1;i<=m;++i)x=read(),y=read(),add(x,y);
for(i=1;i<=n;++i)if(!dnf[i])dfs(i);
for(x=1;x<=n;++x){
if(du[pos[x]])continue;
for(i=h[x];i!=-1;i=ne[i])
if(pos[x]!=pos[to[i]]){du[pos[x]]=1;break;}
}
for(i=1;i<=cn;++i)
if(!du[i]&&!bj)bj=1,ans=js[i];
else if(!du[i]){ans=0;break;}
printf("%d\n",ans);
return 0;
}
T2
期望得分：100 实际得分：100
题目描述：HDU1598
题目分析：把边权从小到大排序，枚举边权最小的边，然后往后处理所有边。对于每一条边，将此边相连的两个点加入同一个并查集，当 s 和 t 属于同一个并查集
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int read(){
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
const int N=205,M=1005;
int n,m,q;
struct node{int x,y,w;}e[M];
int f[N];
bool cmp(node a,node b){return a.w<b.w;}
int find(int x){
if(f[x]==x)return x;
f[x]=find(f[x]);return f[x];
}
int main()
{
freopen("road.in","r",stdin);
freopen("road.out","w",stdout);
int i,j,s,t,ans,r1,r2;
while(~scanf("%d%d",&n,&m)){
for(i=1;i<=m;++i)e[i].x=read(),e[i].y=read(),e[i].w=read();
sort(e+1,e+1+m,cmp);q=read();
while(q--){
s=read(),t=read(),ans=1e9;
for(i=1;i<=m;++i){
for(j=1;j<=n;++j)f[j]=j;
for(j=i;j<=m;++j){
r1=find(e[j].x),r2=find(e[j].y);
if(r1!=r2){
f[r1]=r2;
if(find(s)==find(t)){
if(ans>e[j].w-e[i].w)ans=e[j].w-e[i].w;
break;}
}
}
}
if(ans<1e9)printf("%d\n",ans);
else puts("-1");
}
}
return 0;
}
T3
期望得分：30 实际得分：100（然而是因为数据水）
题目描述：poj1639
题目分析：
我…… 我不会度限制生成树…… 我…… 我在最小生成树的时候判断如果和公园相连的边已经选了 k 条，就不选和公园相连的边了…… 我…… 我 A 了这题……
好吧，说一说正解。
应该看得出题目是一个 Park 度数小于等于 k 的最小生成树吧？
首先，我们去掉所有与 Park 相连的边，假设图被分成了 m 块，那么就弄 m 个最小生成树出来。再选 m 条最小的边让 m 块与 Park 相连，这个时候我们得到了 Park 的最小度生成树。
然后我们添加新的与 Park 相连的边。每次 dfs 一遍生成树，记录 Park 到每一个点的路径上的最长的那一条（当然不能是与 Park 相连的某一条），然后就可以算出添加一条新的与 Park 相连的边可以使当前答案减小的最大值，去掉该去的边，加上该加的边，重复此过程，直到与 Park 相连的边为 k 条或是不能使得答案减小为止。
代码：
#include<algorithm>
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<map>
using namespace std;
int n,m,lim,ans,nowk;
map<string,int>name;
struct node{int x,y,w;}e[405];
int l[25][25],f[25],g[25][25],a[25],pre[25];
bool cmp(node a,node b){return a.w<b.w;}
int find(int x){
if(f[x]==x)return x;
f[x]=find(f[x]);return f[x];
}
void work1(){
int i,r1,r2;
sort(e+1,e+1+m,cmp);
for(i=1;i<=n;++i)f[i]=i;
for(i=1;i<=m;++i){
if(e[i].x==1||e[i].y==1)continue;
r1=find(e[i].x),r2=find(e[i].y);
if(r1!=r2){
f[r1]=r2,ans+=e[i].w;
g[e[i].x][e[i].y]=g[e[i].y][e[i].x]=1;
}
}
}
int dp[25],u[25],v[25];
void dfs(int x,int las){
for(int i=1;i<=n;++i){
if(i==las)continue;
if(!g[x][i])continue;
if(dp[i]!=-1){
if(dp[x]==-1||dp[x]<l[x][i])
dp[i]=l[x][i],u[i]=x,v[i]=i;
else dp[i]=dp[x],u[i]=u[x],v[i]=v[x];
}
dfs(i,x);
}
}
void work2(){
int i,r1,j,mx,bj;
for(i=1;i<=n;++i)a[i]=1e8;
for(i=1;i<=n;++i){
if(l[1][i]==-1)continue;
r1=find(i);if(a[r1]>l[1][i])a[r1]=l[1][i],pre[r1]=i;
}
for(i=1;i<=n;++i)if(pre[i]){
g[1][pre[i]]=g[pre[i]][1]=1;
ans+=l[1][pre[i]],++nowk;
}
for(i=nowk+1;i<=lim;++i){
for(j=1;j<=n;++j){
if(g[1][j])dp[j]=-1;
else dp[j]=0;
}
dfs(1,0),mx=0;
for(j=1;j<=n;++j){
if(l[1][j]==-1||g[1][j])continue;
if(l[1][j]-dp[j]<mx)mx=l[1][j]-dp[j],bj=j;
}
if(mx>=0)break;ans+=mx;
g[u[bj]][v[bj]]=g[v[bj]][u[bj]]=0;
g[1][bj]=g[bj][1]=1;
}
}
int main(){
freopen("park.in","r",stdin);
freopen("park.out","w",stdout);
int i;string s1,s2;
memset(l,-1,sizeof(l));
scanf("%d",&m);name["Park"]=1;n=1;
for(i=1;i<=m;++i){
cin>>s1>>s2>>e[i].w;
if(!name[s1])name[s1]=++n;
if(!name[s2])name[s2]=++n;
e[i].x=name[s1],e[i].y=name[s2];
l[e[i].x][e[i].y]=l[e[i].y][e[i].x]=e[i].w;
}
scanf("%d",&lim);work1();work2();
printf("Total miles driven: %d",ans);
return 0;
}
T4
期望得分：100 实际得分：100
题目描述：poj3463
题目分析-方法 1：
首先在反向图上从 t 开始跑一遍 spfa，得到每一个点到终点的最短路。然后记忆化搜索，f[x] 表示从 x 到 t 的最短路数量，g[x] 表示从 x 到 t 的比最短路长 1 的路的数量，状态转移看代码吧。
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
int read(){
int q=0;char ch=' ';
while(ch<'0'||ch>'9')ch=getchar();
while(ch>='0'&&ch<='9')q=q*10+ch-'0',ch=getchar();
return q;
}
const int N=1005,M=10005;
int tot,n,m,t1,s,t,T;
int h[N],ne[M],to[M],w[M],h1[N],ne1[M],to1[M],w1[M];
int dis[N],inq[N],vis[N];
long long f[N],g[N];
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
void add1(int x,int y,int z)
{to1[++t1]=y,ne1[t1]=h1[x],h1[x]=t1,w1[t1]=z;}
void spfa(){
queue<int>q;int i,x;
for(i=1;i<=n;++i)dis[i]=1e8,inq[i]=0;
dis[t]=0,q.push(t);
while(!q.empty()){
x=q.front(),q.pop(),inq[x]=0;
for(i=h1[x];i!=-1;i=ne1[i])
if(dis[x]+w1[i]<dis[to1[i]]){
dis[to1[i]]=dis[x]+w1[i];
if(!inq[to1[i]])inq[to1[i]]=1,q.push(to1[i]);
}
}
}
void dfs(int x){
if(vis[x])return;
vis[x]=1;if(x==t)return;
for(int i=h[x];i!=-1;i=ne[i]){
if(w[i]+dis[to[i]]==dis[x])
dfs(to[i]),g[x]+=g[to[i]],f[x]+=f[to[i]];
else if(w[i]+dis[to[i]]==dis[x]+1)
dfs(to[i]),g[x]+=f[to[i]];
}
}
int main()
{
freopen("travel.in","r",stdin);
freopen("travel.out","w",stdout);
int i,x,y,z;
T=read();
while(T--){
n=read(),m=read();tot=t1=0;
for(i=1;i<=n;++i)h[i]=h1[i]=-1,f[i]=g[i]=vis[i]=0;
for(i=1;i<=m;++i){
x=read(),y=read(),z=read();
add(x,y,z),add1(y,x,z);
}
s=read(),t=read();spfa();
if(dis[s]>=1e8){puts("0");return 0;}
f[t]=1;dfs(s);
printf("%lld\n",f[s]+g[s]);
}
return 0;
}
题目分析-方法 2**：
呃，所以为什么其他人都是在 dijkstra 的时候顺便求次短路和计数呐？
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=1005,M=10005;
int T,tot,n,m,s,t;
int h[N],ne[M],to[M],w[M];
void add(int x,int y,int z)
{to[++tot]=y,ne[tot]=h[x],h[x]=tot,w[tot]=z;}
int dis[N][2],c[N][2],vis[N][2];
void work(){
int i,j,flag,k,mx,l,v;
for(i=1;i<=n;++i){
dis[i][0]=dis[i][1]=1e8;
c[i][0]=c[i][1]=vis[i][0]=vis[i][1]=0;
}
dis[s][0]=0,c[s][0]=1;
for(i=1;i<=2*n-1;++i){
k=-1,mx=1e8;
for(j=1;j<=n;++j)
if(!vis[j][0]&&dis[j][0]<mx)
mx=dis[j][0],k=j,flag=0;
else if(!vis[j][1]&&dis[j][1]<mx)
mx=dis[j][1],k=j,flag=1;
if(k==-1)break;
vis[k][flag]=1;
for(j=h[k];j!=-1;j=ne[j]){
l=dis[k][flag]+w[j],v=to[j];
if(l<dis[v][0]){
dis[v][1]=dis[v][0],c[v][1]=c[v][0];
dis[v][0]=l,c[v][0]=c[k][flag];
}
else if(l==dis[v][0])c[v][0]+=c[k][flag];
else if(l<dis[v][1])dis[v][1]=l,c[v][1]=c[k][flag];
else if(l==dis[v][1])c[v][1]+=c[k][flag];
}
}
}
int main(){
int i,x,y,z;
scanf("%d",&T);
while(T--){
memset(h,-1,sizeof(h));tot=0;
scanf("%d%d",&n,&m);
for(i=1;i<=m;++i)scanf("%d%d%d",&x,&y,&z),add(x,y,z);
scanf("%d%d",&s,&t);work();
if(dis[t][1]==dis[t][0]+1)c[t][0]+=c[t][1];
printf("%d\n",c[t][0]);
}
return 0;
}
0 条评论