今天的主要内容为最小生成树、判负环和差分约束系统
苗条的最小生成树 poj3522
本题排序完枚举最小边，Kruskal跑n遍即可。
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; const int INF=0x7fffffff; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<3)+(num<<1)+c-‘0‘;c=getchar();} return num*t; } struct edge{int u,v,c;}e[5000]; int fa[5000],V,E; bool cmp(edge a,edge b){return a.c<b.c;} int find(int x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } void unite(int x,int y){ int fx=find(x),fy=find(y); if(fx==fy)return; fa[fx]=fy; } int kruskal(){ sort(e+1,e+1+E,cmp);int ans=INF; for(int i=1;i<=E;i++){ for(int j=1;j<=V;j++)fa[j]=j;int cnt=V; for(int j=i;j<=E;j++) if(find(e[j].u)!=find(e[j].v)){ unite(e[j].u,e[j].v); if(--cnt==1){ ans=min(ans,e[j].c-e[i].c);break; } } } if(ans==INF)ans=-1; return ans; } int main() { while(1){ V=read();E=read(); if(V==0)break; for(int i=1;i<=E;i++){ int u=read(),v=read(),c=read(); e[i]=(edge){u,v,c}; } printf("%d\n",kruskal()); } return 0; }
虫洞 9018_1449
题目大意是给出m条正边，w条负的，叫你判负环
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<3)+(num<<1)+c-‘0‘;c=getchar();} return num*t; } const int INF=1000000000; struct edge{int v,c;}; vector<edge>g[1510]; int T,n,m,w,cnt[510],lev[510]; void solve(){ queue<int>q; q.push(1);cnt[1]++;lev[1]=0; while(!q.empty()){ int x=q.front();q.pop(); if(cnt[x]>n){puts("YES");return;} for(int i=0;i<g[x].size();i++){ edge y=g[x][i]; if(lev[x]+y.c<lev[y.v]){ lev[y.v]=lev[x]+y.c; q.push(y.v);cnt[y.v]++; } } } puts("NO"); } int main() { T=read(); while(T--){ n=read();m=read();w=read(); for(int i=1;i<=n;i++)g[i].clear(); for(int i=1;i<=n;i++)lev[i]=INF; memset(cnt,0,sizeof(cnt)); for(int i=1;i<=m;i++){ int u=read(),v=read(),c=read(); g[u].push_back((edge){v,c}); g[v].push_back((edge){u,c}); } for(int i=1;i<=w;i++){ int u=read(),v=read(),c=read(); g[u].push_back((edge){v,-c}); } solve(); } return 0; }
layout 9018_1456
本题在判负环的基础上用了差分约束系统
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<3)+(num<<1)+c-‘0‘;c=getchar();} return num*t; } const int INF=1000000000; struct edge{int v,c;};vector<edge>g[3010]; int T,n,m,w,cnt[1010],lev[1010]; void solve(){ queue<int>q;q.push(1);cnt[1]++;lev[1]=0; while(!q.empty()){ int x=q.front();q.pop(); if(cnt[x]>n){if(lev[1]<0)puts("-1");else puts("-2");return;} for(int i=0;i<g[x].size();i++){ edge y=g[x][i]; if(lev[x]+y.c<lev[y.v]){lev[y.v]=lev[x]+y.c;q.push(y.v);cnt[y.v]++;} } } printf("%d\n",lev[n]); } int main() { n=read();m=read();w=read(); for(int i=1;i<=n;i++)lev[i]=INF,g[i].clear(); memset(cnt,0,sizeof(cnt)); for(int i=2;i<=n;i++)g[i].push_back((edge){i-1,0}); for(int i=1;i<=m;i++){ int u=read(),v=read(),c=read(); g[u].push_back((edge){v,c}); } for(int i=1;i<=w;i++){ int u=read(),v=read(),c=read(); g[v].push_back((edge){u,-c}); }solve(); return 0; }
糖果BZOJ2330
本题思路和上题差不多
注意的时
是如果用vector的话由0向各个点的边要从1——n连
~~~~~编表~~~~~~~~~~~~~~~~~~~~~~n——1连
我一不小心vector的连边顺序变成n——1 然后就T了
#include<iostream> #include<cstdio> #include<vector> #include<queue> #include<cstring> #include<algorithm> using namespace std; inline int read(){ int num=0,t=1;char c=getchar(); while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){num=(num<<3)+(num<<1)+c-‘0‘;c=getchar();} return num*t; } const int INF=1000000000; struct edge{int v,c;}; vector<edge>g[205010];queue<int>q; int n,k,cnt[100010]={0},lev[100010]={0},du[100010]={0}; void add(int x,int y,int c){g[x].push_back((edge){y,c});} bool solve(){ q.push(0);cnt[0]++;lev[0]=0; while(!q.empty()){ int x=q.front();q.pop(); if(cnt[x]>n)return 1; for(int i=0;i<g[x].size();i++){ edge y=g[x][i]; if(lev[x]+y.c>lev[y.v]){ lev[y.v]=lev[x]+y.c; q.push(y.v);cnt[y.v]++; } } } return 0; } int main() { n=read();k=read(); for(int i=1;i<=k;i++){ int x=read(),a=read(),b=read(); if(x==1){add(a,b,0),add(b,a,0);} else if(x==2){if(a==b){puts("-1");return 0;}add(a,b,1);} else if(x==3)add(b,a,0); else if(x==4){if(a==b){puts("-1");return 0;}add(b,a,1);} else add(a,b,0); } for(int i=1;i<=n;i++)add(0,i,1); if(solve()){puts("-1");return 0;} long long ans=0; for(int i=1;i<=n;i++)ans+=lev[i]; printf("%lld\n",ans); return 0; }
本文由Yzyet编写，网址为www.cnblogs.com/Yzyet。非Yzyet同意，禁止转载，侵权者必究。
原文：http://www.cnblogs.com/Yzyet/p/7123747.html