범죄 자 를 수감 하 는 두 가지 방법
5042 단어 병 찰 집
S 타 운 에는 현재 두 개의 교도소 가 있 으 며, 모두 N 명의 범죄자 가 수감 되 어 있 으 며, 번 호 는 각각 1 ~ N 이다.그들 사이 의 관계 도 자연히 극 에 달 했다
불협화음.많은 범죄자 들 사이 에 원한 이 쌓 여 객관 적 인 조건 이 갖 춰 지면 언제 든 충돌 이 일어 날 수 있다.원망 하 다
'기 치' (하나의 정수 치) 는 특정한 두 명의 범죄자 간 의 원한 정 도 를 나타 내 고 원한 이 클 수록 이 두 명의 범인 을 나타 낸다.
쌓 인 원한 이 많 을 수록.만약 두 명의 원한 이 c 인 범죄자 가 같은 감옥 에 갇 히 면 그들 둘 사이 에 마찰 이 생 길 것 이다.
영향력 c 의 충돌 사건 을 야기 하 다.
매년 말 경찰 서 는 올해 안에 감옥 에 있 는 모든 충돌 사건 을 영향력 에 따라 큰 것 부터 작은 것 까지 목록 을 만든다.
그리고 S 성 Z 시장 한테 보고 해.공무 가 바 쁜 Z 시장 은 리스트 에 있 는 첫 번 째 사건 의 영향력 만 본다.
만약 영향 이 매우 나쁘다 면, 그 는 경찰국장 의 경질 을 고려 할 것 이다.
N 명 범죄자 간 갈등 관 계 를 상세히 살 펴 본 경찰 국장 은 스트레스 를 크게 받 았 다.그 는 범인 들 을
두 감옥 은 충돌 사건 의 영향력 이 작 아 자신의 감 투 를 지 키 기 위해 재분배 되 었 다.가령
같은 감옥 에 있 는 두 범죄자 사이 에 원한 이 있다 면 그들 은 매년 어느 순간 마찰 을 일 으 킬 것 이다.그럼.
Z 시장 이 본 그 충돌 사건 의 영향력 을 최소 화 할 수 있 는 범인 을 어떻게 분배 해 야 할 까?이 최소 치 는 적 습 니까?
입력 설명 Input Description
첫 번 째 행 위 는 두 개의 정수 N 과 M 으로 각각 범인의 수 와 원한 이 있 는 범인의 대 수 를 나타 낸다.
다음 M 행 의 모든 행 위 는 세 개의 정수 aj, bj, cj 로 aj 호 와 bj 호 범죄자 사이 에 원한 이 존재 하고 그 원한 치 는 cj 임 을 나타 낸다.데이터 보증, 그리고 범죄자 조합 은 한 번 만 나타난다.
출력 설명 Output Description
모두 1 행 으로 Z 시장 이 본 그 충돌 사건 의 영향력.하면, 만약, 만약...
충돌 사건 이 발생 하지 않 았 습 니 다. 0 을 출력 하 십시오.
샘플 입력 Sample Input
4 6
1 4 2534
2 3 3512
1 2 28351
1 3 6618
2 4 1805
3 4 12884
샘플 출력 Sample Output
3512
데이터 범위 및 알림 Data Size & Hint
범죄자 간 의 원한 치 는 아래 왼쪽 그림 에서 보 듯 이 오른쪽 그림 은 범죄자 의 분배 방법 으로 시장 이 본 충돌 사건 이다.
영향력 은 3512 (2 번 과 3 번 범죄자 로 인 한) 다.다른 어떤 분 법 도 이 분 법보 다 더 좋 을 수 없다.
【 데이터 범위 】
30% 의 데 이 터 는 N ≤ 15 입 니 다.
70% 의 데 이 터 는 N ≤ 2000, M ≤ 50000 입 니 다.
100% 의 데 이 터 는 N ≤ 20000, M ≤ 100000 입 니 다.
『 33951 』 은 쓰 고 집 만 찾 아 요 ~ ~ ~ (>
단계:
1. 크 고 작은 순서 로 영향 치 를 정렬 하고 모든 사람의 아버 지 를 자신 으로 설정 합 니 다 (기본 동작 을 수집 하고 배우 지 않 습 니 다)
2. 차례차례 판단
(1) 만약 에 두 사람 이 같은 집합 을 한다 면 그들의 영향 치가 가장 클 것 이다.
//즉, 두 사람 을 서로 다른 집합 에 두 면 반드시 이전의 특정한 것 과 충돌 해 야 한다. 큰 것 에서 작은 것 으로 순 서 를 매 기 는 것 이기 때문에 앞의 영향 치 는 반드시 뒤에 있 기 때문에 현재 의 영향 치 는 최대 치 를 만족 시 키 는 것 이 가장 적다.
(2) 만약 에 두 사람 이 대립 집합 이 있 으 면 x 와 y 의 대립 집합 을 합병 하고 y 와 x 의 대립 집합 을 합병 한다.
(3) 만약 에 두 사람 중 어느 한 사람 이 대립 집합 이 있 으 면 대립 집합 과 대립 집합 이 없 는 범죄 자 를 합병 하고 대립 집합 이 없 는 범죄자 의 대립 집합 을 다른 범죄자 로 설정한다.
(4) 만약 에 두 사람 이 대립 집합 이 없 으 면 서로 대립 집합 으로 설정한다.
3. 프로그램 이 종료 되 지 않 았 다 면 0 을 출력 합 니 다.
코드 붙 이기:
#include
#include
#include
#include
#include
using namespace std;
struct Node{
int x,y,z;
}a[100005];
int n,m,e[20001],f[20001];
int cmp(Node x,Node y)
{
return x.z>y.z;
}
int Find(int x)
{
return x==f[x]? x:f[x]=Find(f[x]);
}
void Union(int x,int y)
{
int fx=Find(x);
int fy=Find(y);
f[f[x]]=fy;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
f[i]=i;
for(int i=1;i<=m;i++)
scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].z);
sort(a+1,a+1+m,cmp);
for(int i=1;i<=m;i++)
{
if(Find(a[i].x)==Find(a[i].y))
{
printf("%d
",a[i].z);
return 0;
}
if(e[a[i].x]!=0&&e[a[i].y]!=0)
{
Union(e[a[i].x],a[i].y);
Union(a[i].x,e[a[i].y]);
}
else
if(e[a[i].x]!=0&&e[a[i].y]==0)
{
e[a[i].y]=a[i].x;
Union(e[a[i].x],a[i].y);
}
else
if(e[a[i].x]==0&&e[a[i].y]!=0)
{
e[a[i].x]=a[i].y;
Union(e[a[i].y],a[i].x);
}
else
if(e[a[i].x]==0&&e[a[i].y]==0)
{
e[a[i].x]=a[i].y;
e[a[i].y]=a[i].x;
}
}
printf("0
");
return 0;
}
이분법
앞 에 별 에 정 보 를 저장 하고 a 배열 로 원한 값 을 따로 저장 하 며 0 (충돌 이 없 으 면 0 을 출력 합 니 다.
a 배열 을 작은 것 부터 큰 것 까지 정렬 하고 두 개의 답 을 주세요.
만약 에 현재 mid 와 같은 관계 가 2 분 그림 의 요 구 를 만족 시 킬 수 있다 면 (2 분 그림 염색 판정 을 사용) 은 mid, r = mid 보다 작 음 을 설명 하고 그렇지 않 으 면 설명 이 mid 보다 크 면 L 대 가 를 mid + 1 로 한다.
다음은 코드:
#include
#include
#include
#include
using namespace std;
struct Node{
int y,z,next;
}e[200020];
int tot,item,n,m;
int head[20005],b[20005],a[100005];
bool pd;
int cmp(int a,int b){return aitem)
{
if(b[e[i].y]==-1)dfs(e[i].y,1-data);
else
if(b[e[i].y]==data){pd=false;return;}
}
}
}
bool work(int midd)
{
memset(b,-1,sizeof(b));
pd=true;
item=a[midd];
for(int i=1;i<=n;i++)
if(b[i]==-1)dfs(i,0);
return pd;
}
int main()
{
scanf("%d%d",&n,&m);
memset(head,0,sizeof(head));
int x,y,z;
tot=0;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&z);
insert(x,y,z);
insert(y,x,z);
a[i+1]=z;
}
// for(int i=1;i<=tot;i++)cout<
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
항 저 우 전기 1878 오 라 회 로 (오 라 회 로 의 판단)오 라 회 로 는 펜 이 지면 을 떠 나 지 못 하 게 그림 의 각 변 을 한 번 만 그 릴 수 있 고 출발점 으로 돌아 갈 수 있 는 회 로 를 말한다.이제 오 라 회 로 가 있 는 지 그림 을 정 해 주 시 겠 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.