首页 > 代码库 > 图论练习们~
图论练习们~
/* hdu 1599 ( find the mincost route ) Floyed求最小环每个环一定是 由 i j k 构成假设k是环中的max 要成环 就要保证不是链(md废话) 利用Floyed的最外层循环含义 i-j最短路经过的点编号<k 那个我们在 限制i<j<k 那么f[i][j]+g[i][k]+g[k][j]一定能构成一个环 并且点数>=3 因为i j k 互不相同 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 110#define inf 2000000using namespace std;int n,m,f[maxn][maxn],g[maxn][maxn],ans;void Clear(){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=g[i][j]=inf; ans=inf;}int min(int x,int y){ return x<y?x:y;}void Floyed(){ for(int k=1;k<=n;k++){ for(int i=1;i<k;i++) for(int j=i+1;j<k;j++) ans=min(ans,f[i][j]+g[i][k]+g[k][j]); for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]); }}int main(){ while(~scanf("%d%d",&n,&m)){ Clear();int u,v,t; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&t); f[u][v]=min(f[u][v],t); f[v][u]=min(f[v][u],t); g[u][v]=g[v][u]=f[u][v]; } Floyed(); if(ans==inf)printf("It‘s impossible.\n"); else printf("%d\n",ans); } return 0;}
/*hdu 2807 ( The Shortest Path ) n*n判断矩阵相乘是不是等于另一矩阵比较快的矩阵比较方法 get了 */#include<iostream>#include<cstdio>#include<cstring>#define maxn 81#define inf 0x3f3f3f3fusing namespace std;int n,m,Q,A[maxn][maxn],f[maxn][maxn],B[maxn];struct node{ int c[maxn][maxn];}p[maxn];void Clear(){ for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) A[i][j]=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=inf; }void Insert(int x,int y){ for(int i=1;i<=m;i++)B[i]=0; for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) B[i]+=p[x].c[i][j]*A[y][j]; int falg=0; for(int k=1;k<=n;k++){ if(k==x||k==y)continue; falg=0; for(int i=1;i<=m;i++) if(A[k][i]!=B[i]){ falg=1;break; } if(!falg)f[x][k]=1; }}void Floyed(){ for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}int main(){ while(1){ scanf("%d%d",&n,&m); if(n==0&&m==0)break; Clear();int u,v; for(int k=1;k<=n;k++) for(int i=1;i<=m;i++) for(int j=1;j<=m;j++){ scanf("%d",&p[k].c[i][j]); A[k][i]+=p[k].c[i][j]*j; } for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) Insert(i,j); Floyed(); scanf("%d",&Q); while(Q--){ scanf("%d%d",&u,&v); if(f[u][v]==inf)printf("Sorry\n"); else printf("%d\n",f[u][v]); } } return 0;}
/* hdu 2224 ( The shortest path ) 不知道为啥出现在最短路分类里 我纯dp做的 */#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<algorithm>#define maxn 210#define inf 0x3f3f3f3fusing namespace std;int n;double x[maxn],y[maxn],g[maxn][maxn],f[maxn][maxn],ans;struct point{ double x,y;}p[maxn];int cmp(const point &a,const point &b){ return a.x<b.x;}void Clear(){ for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) f[i][j]=inf; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) g[i][j]=inf; ans=inf;}double Get(int i,int j){ return sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x)+(p[i].y-p[j].y)*(p[i].y-p[j].y));}int max(int a,int b){ return a>b?a:b;}int main(){ while(scanf("%d",&n)!=EOF){ Clear(); for(int i=1;i<=n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); sort(p+1,p+1+n,cmp); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) g[i][j]=g[j][i]=Get(i,j); f[1][1]=0; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ int k=max(i,j)+1; f[i][k]=min(f[i][k],f[i][j]+g[j][k]); f[k][j]=min(f[k][j],f[i][j]+g[i][k]); } for(int i=1;i<=n;i++){ ans=min(ans,f[i][n]+g[i][n]); ans=min(ans,f[n][i]+g[n][i]); } printf("%.2f\n",ans); } return 0; }
/*hdu 1598 ( find the most comfortable road ) 再次被分类坑了...是并茶几不是最短路..枚举每组数据所用的最小的边-最大的边有点慢 不过还好并茶几飞快 */#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 1010using namespace std;int n,m,Q,fa[maxn],mx;struct node{ int u,v,t; bool operator < (const node &a) const { return t<a.t; }}e[maxn];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x];}int min(int x,int y){ return x<y?x:y;}int main(){ while(~scanf("%d%d",&n,&m)){ int u,v,t; for(int i=1;i<=m;i++){ u=init();v=init();t=init(); e[i].u=u;e[i].v=v;e[i].t=t; } sort(e+1,e+1+m); Q=init(); while(Q--){ u=init();v=init();mx=0x7fffffff; for(int k=1;k<=m;k++){ for(int i=1;i<=n;i++)fa[i]=i; for(int i=k;i<=m;i++){ int r1=find(e[i].u); int r2=find(e[i].v); if(r1!=r2)fa[r2]=r1; if(find(u)==find(v)){ mx=min(mx,e[i].t-e[k].t);break; } } } if(mx==0x7fffffff)printf("-1\n"); else printf("%d\n",mx); } } return 0;}
/*+几条边不存在桥*/#include<iostream>#include<cstdio>#include<stack>#include<cstring>#define maxn 1010using namespace std;int n,m,num,head[maxn],low[maxn],dfn[maxn],topt,f[maxn],r[maxn],sum,belong[maxn];stack<int>s;struct node{ int v,pre;}e[maxn*2];int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Clear(){ num=0;topt=0;sum=0; for(int i=0;i<=n;i++)f[i]=0; for(int i=0;i<=n;i++)r[i]=0; for(int i=0;i<=n;i++)low[i]=0; for(int i=0;i<=n;i++)dfn[i]=0; for(int i=0;i<=n;i++)head[i]=-1; for(int i=0;i<=n;i++)belong[i]=0; while(!s.empty())s.pop();}void Add(int from,int to){ e[num].v=to; e[num].pre=head[from]; head[from]=num++;}void Dfs(int x,int from){ low[x]=dfn[x]=++topt; f[x]=1;s.push(x); for(int i=head[x];i!=-1;i=e[i].pre){ int v=e[i].v; if(i==(from^1))continue; if(dfn[v]==0){ Dfs(v,i);low[x]=min(low[x],low[v]); } else if(f[v])low[x]=min(low[x],dfn[v]); } if(low[x]==dfn[x]){ sum++; while(s.top()!=x){ belong[s.top()]=sum;f[s.top()]=0;s.pop(); } belong[s.top()]=sum;f[s.top()]=0;s.pop(); }}int main(){ while(~scanf("%d%d",&n,&m)){ Clear();int u,v; for(int i=1;i<=m;i++){ u=init();v=init(); Add(u,v);Add(v,u); } for(int i=1;i<=n;i++) if(dfn[i]==0)Dfs(i,-1); for(int u=1;u<=n;u++) for(int i=head[u];i!=-1;i=e[i].pre){ int v=e[i].v; if(belong[u]!=belong[v])r[belong[u]]++; } int cnt=0; for(int i=1;i<=sum;i++) if(r[i]==1)cnt++; printf("%d\n",(cnt+1)/2); } return 0;}
/*hdu 3768 ( Shopping ) SPFA+全排列*/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define maxn 200010using namespace std;int T,n,m,k,c[20],num,head[maxn],dis[maxn],g[20][20],f[maxn],a[20];long long ans;struct node{ int v,t,pre;}e[maxn*10];queue<int>q;int init(){ int x=0,f=1;char s=getchar(); while(s<‘0‘||s>‘9‘){if(s==‘-‘)f=-1;s=getchar();} while(s>=‘0‘&&s<=‘9‘){x=x*10+s-‘0‘;s=getchar();} return x*f;}void Clear(){ num=0;ans=0x7fffffff; memset(head,0,sizeof(head)); memset(g,127/3,sizeof(g)); memset(a,0,sizeof(a)); memset(c,0,sizeof(c));}void Add(int from,int to,int dis){ num++;e[num].v=to; e[num].t=dis; e[num].pre=head[from]; head[from]=num;}void SPFA(int s){ memset(dis,127/3,sizeof(dis)); memset(f,0,sizeof(f)); dis[s]=0;f[s]=1;q.push(s); while(!q.empty()){ int u=q.front(); f[u]=0;q.pop(); for(int i=head[u];i;i=e[i].pre){ int v=e[i].v; if(dis[v]>dis[u]+e[i].t){ dis[v]=dis[u]+e[i].t; if(f[v]==0){ f[v]=1;q.push(v); } } } }}int main(){ T=init(); while(T--){ n=init();m=init(); Clear();int u,v,t; for(int i=1;i<=m;i++){ u=init();v=init();t=init(); Add(u,v,t);Add(v,u,t); } k=init(); for(int i=1;i<=k;i++){ c[i]=init();a[i]=i; } SPFA(0); for(int i=1;i<=k;i++) g[0][i]=g[i][0]=dis[c[i]]; for(int i=1;i<=k;i++){ SPFA(c[i]); for(int j=1;j<=k;j++) g[i][j]=dis[c[j]]; } do{ long long mx=0; for(int i=1;i<=k+1;i++) mx+=g[a[i-1]][a[i]]; ans=min(ans,mx); }while(next_permutation(a+1,a+k+1)); cout<<ans<<endl; } return 0;}
/*poj 1679 次小生成树n*n算法 get了*/#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#define maxn 110using namespace std;int T,n,m,num,head[maxn],fa[maxn],c[maxn*maxn],mx[maxn][maxn],mst,ans;struct node{ int u,v,t,o; bool operator < (const node &x) const{ return t<x.t; }}p[maxn*maxn];struct edge{ int v,t,pre,x;}e[maxn*maxn*2];void Clear(){ num=mst=0;ans=0x7fffffff; for(int i=0;i<=n;i++)fa[i]=i; for(int i=0;i<=n;i++) for(int j=0;j<=n;j++) mx[i][j]=0; for(int i=0;i<=m;i++)c[i]=0; for(int i=0;i<=n;i++)head[i]=0;}void Add(int from,int to,int dis,int numb){ num++;e[num].v=to; e[num].t=dis; e[num].x=numb; e[num].pre=head[from]; head[from]=num;}int find(int x){ if(x!=fa[x])fa[x]=find(fa[x]); return fa[x];}void MST(){ int tot=0; for(int i=1;i<=m;i++){ int r1=find(p[i].u); int r2=find(p[i].v); if(r1!=r2){ tot++;mst+=p[i].t; c[p[i].o]=1;fa[r2]=r1; } if(tot==n-1)break; }}void Dfs(int s,int now,int from,int mxx){ mx[s][now]=mxx; for(int i=head[now];i;i=e[i].pre){ int v=e[i].v; if(v==from)continue; if(c[e[i].x]==0)continue; Dfs(s,v,now,max(mxx,e[i].t)); }}void Mx(){ for(int i=1;i<=n;i++) Dfs(i,i,-1,0);}int main(){ scanf("%d",&T); while(T--){ scanf("%d%d",&n,&m); Clear();int u,v,t; for(int i=1;i<=m;i++){ scanf("%d%d%d",&u,&v,&t); Add(u,v,t,i);Add(v,u,t,i); p[i].u=u;p[i].v=v; p[i].t=t;p[i].o=i; } sort(p+1,p+1+m); MST();Mx(); for(int i=1;i<=m;i++){ if(c[p[i].o])continue; int len=mx[p[i].u][p[i].v]; ans=min(ans,mst+p[i].t-len); } if(ans==mst)printf("Not Unique!\n"); else printf("%d\n",mst); } return 0;}
图论练习们~
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。