首页 > 其他 > 详细

暑假集训day5

时间:2017-07-05 22:45:27      阅读:344      评论:0      收藏:0      [点我收藏+]

今天的主要内容为最小生成树判负环差分约束系统

 

苗条的最小生成树 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同意,禁止转载,侵权者必究。

暑假集训day5

原文:http://www.cnblogs.com/Yzyet/p/7123747.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!