[SCOI 2011] 사탕 차별 제약
차분 제약 누드 문제, 내 코드는 항상 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;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
HDU 3631 Shortest Path(Floyd + 플러그인)제목: n개의 점 m줄 테두리(단방향 테두리)와 q차 조작을 드리겠습니다. 처음에는 모든 점이 표시가 없습니다. 두 가지 조작이 있습니다. 1.0 x: x를 표시하고 가까이 표시한 경우 "ERROR! At point...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.