# 20171012 图论 test3

## T1

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
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;
for(i=1;i<=n;++i)h[i]=-1;
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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
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()
{
int i,j,s,t,ans,r1,r2;
while(~scanf("%d%d",&n,&m)){
while(q--){
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

#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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
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;
while(T--){
for(i=1;i<=n;++i)h[i]=h1[i]=-1,f[i]=g[i]=vis[i]=0;
for(i=1;i<=m;++i){
}
if(dis[s]>=1e8){puts("0");return 0;}
f[t]=1;dfs(s);
printf("%lld\n",f[s]+g[s]);
}
return 0;
}


#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);
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;
}