POJ 3228 골 드 교통 (2 점 + 최대 흐름)
이 문 제 는 이전 문제 와 헷 갈 려 서 느낌 이 똑 같 아서 생각 도 못 하고 뜯 어서 최 단 로 를 구하 고 2 점 으로 최대 흐름 을 구 했다.결 과 는 샘플 에 도 못 미 치고 또 어디 손 이 못 된 줄 알 았 다.결국 사례 를 보 니 손 으로 계산 하 는 것 도 틀 렸 다.나중에 뜯 지 않 고 원점 에 직접 만 든 그림 은 결국 사례 가 지나 갔다.그리고 AC 1 회 제출...
나중에 곰 곰 이 생각해 보 니 이 문 제 는 모든 길이 가장 짧 은 것 이지 전체 가 가장 짧 은 것 이 아니다.그 러 니까 뜯 으 면 안 된다 는 거 야.내 가 섞 은 그 문제 (poj 2391) 는 다 물 어 본 총 최소 치 였 다.
이 문제 의 건축 도 는 바로 원점 과 외환 점 을 건설 하여 모든 금광 과 원점 을 연결 시 키 는 것 이다. 가중치 는 금광 수 이 고 외환 점 과 도 연결 되 며 가중치 는 창고 용량 이다.그리고 2 분 의 최대 거 리 는 2 분 의 거리 보다 작은 연결 변 이다.마지막 으로 만 류 여 부 를 판단 하 다.
코드 는 다음 과 같 습 니 다:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <algorithm>
using namespace std;
const int INF=1e9;
int head[500], s, t, nv, cnt, sum;
int num[500], d[500], pre[500], cur[500], q[500], g1[500], g2[500], mp[210][210];
struct node
{
int u, v, cap, next;
}edge[1000000];
void add(int u, int v, int cap)
{
edge[cnt].v=v;
edge[cnt].cap=cap;
edge[cnt].next=head[u];
head[u]=cnt++;
edge[cnt].v=u;
edge[cnt].cap=cap;
edge[cnt].next=head[v];
head[v]=cnt++;
}
void bfs()
{
memset(d,-1,sizeof(d));
memset(num,0,sizeof(num));
int f1=0, f2=0, i;
q[f1++]=t;
num[0]=1;
d[t]=0;
while(f1>=f2)
{
int u=q[f2++];
for(i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(d[v]==-1)
{
d[v]=d[u]+1;
num[d[v]]++;
q[f1++]=v;
}
}
}
}
int isap()
{
memcpy(cur,head,sizeof(cur));
int flow=0, u=pre[s]=s, i;
bfs();
while(d[s]<nv)
{
if(u==t)
{
int f=INF, pos;
for(i=s;i!=t;i=edge[cur[i]].v)
{
if(f>edge[cur[i]].cap)
{
f=edge[cur[i]].cap;
pos=i;
}
}
for(i=s;i!=t;i=edge[cur[i]].v)
{
edge[cur[i]].cap-=f;
edge[cur[i]^1].cap+=f;
}
flow+=f;
if(flow>=sum)
return flow;
u=pos;
}
for(i=cur[u];i!=-1;i=edge[i].next)
{
if(d[edge[i].v]+1==d[u]&&edge[i].cap)
{
break;
}
}
if(i!=-1)
{
cur[u]=i;
pre[edge[i].v]=u;
u=edge[i].v;
}
else
{
if(--num[d[u]]==0) break;
int mind=nv;
for(i=head[u];i!=-1;i=edge[i].next)
{
if(mind>d[edge[i].v]&&edge[i].cap)
{
mind=d[edge[i].v];
cur[u]=i;
}
}
d[u]=mind+1;
num[d[u]]++;
u=pre[u];
}
}
return flow;
}
int main()
{
int n, m, a, b, c, i, j, x, y;
while(scanf("%d",&n)!=EOF&&n)
{
sum=0;
y=0;
for(i=1;i<=n;i++)
{
scanf("%d",&g1[i]);
sum+=g1[i];
}
for(i=1;i<=n;i++)
{
scanf("%d",&g2[i]);
y+=g2[i];
}
scanf("%d",&m);
memset(mp,9999999,sizeof(mp));
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
if(mp[a][b]>c)
mp[a][b]=mp[b][a]=c;
}
/*for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",mp[i][j]);
}
printf("
");
}*/
if(y<sum)
{
printf("No Solution
");
continue ;
}
int high=2000000, mid, low=1, ans=-1;
while(low<=high)
{
mid=(low+high)/2;
s=0;
t=2*n+1;
nv=t+1;
memset(head,-1,sizeof(head));
cnt=0;
for(i=1;i<=n;i++)
{
add(s,i,g1[i]);
add(i,t,g2[i]);
for(j=1;j<i;j++)
{
if(mp[i][j]<=mid)
{
add(i,j,INF);
}
}
}
x=isap();
//printf("---%d
",x);
if(x>=sum)
{
ans=mid;
high=mid-1;
}
else
{
low=mid+1;
}
}
if(ans==-1)
printf("No Solution
");
else
printf("%d
",ans);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.