[SCOI 2011] 사탕 차별 제약

bzoj2330
차분 제약 누드 문제, 내 코드는 항상 T점 하나, 황 선배와 여러 번 비교해도 별 차이가 없어...[그 체인의 테스트 포인트가 아니다]
A 없이 파렴치하게 코드를 보낸 사람의 코드:
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int SIZE=100010;
int head[SIZE],nxt[SIZE*4],tot=0;
typedef long long LL;

int dist[SIZE];

struct edge{
    int t,d;
}l[SIZE*4];

inline void build(int f,int t,int d)
{
    l[++tot]=(edge){t,d};
    nxt[tot]=head[f];
    head[f]=tot; 
} 
int n,m;

int q[SIZE];
bool use[SIZE],t[SIZE];
inline bool spfa(int s)
{
    dist[s]=1;
    use[s]=1;
    int l=0,r=1;
    q[l]=s;
    while(l!=r)
    {
        int f=q[l]; l++; if(l==SIZE) l=0;
        use[f]=0;
        for(int i=head[f];i;i=nxt[i])
        {
            int v=::l[i].t;
            if(dist[v]<dist[f]+::l[i].d) 
            {
                dist[v]=dist[f]+::l[i].d;
                if(!use[v])
                {
                    use[v]=1;
                    q[r++]=v; if(r==SIZE) r=0;
                    t[v]++;
                    if(t[v]>n) return false;
                }
            }
        }
    }
    return true;
}
inline void scan(int &n)
{
    n=0;
    char a=getchar();
    while(a>'9'||a<'0') a=getchar();
    while(a<='9'&&a>='0') n*=10,n+=a-'0',a=getchar();
}

int main()
{
    scan(n);    scan(m);
    //scanf("%d%d",&n,&m);
    while(m--)
    {
        int x,a,b;
        scan(x);    scan(a);    scan(b);
        //scanf("%d%d%d",&x,&a,&b);
        switch(x)
        {
            case 1: build(a,b,0);build(b,a,0);  break;  //a==b
            case 2: if(a==b) {printf("-1");return 0;}
                build(a,b,1);                   break;                  //a<b b-a>0 b-a>=1

            case 3: build(b,a,0);               break;      //a>=b a-b>=0
            case 4: if(a==b) {printf("-1");return 0;}
                build(b,a,1);                   break;                  //a>b a-b>0 a-b>=1
            case 5: build(a,b,0);               break;                  //a<=b b-a>=0 
        }
    }

    for(int i=n;i>=1;i--)
    {
        build(0,i,0);
    }

    if(!spfa(0))
    {
        printf("-1");
        return 0;
    }
    LL ans=0; 
    for(int i=1;i<=n;i++) //printf("%lld ",dist[i]),
        ans+=dist[i];
    printf("%lld",ans);
    return 0;
}

좋은 웹페이지 즐겨찾기