poj 1815 Friendship (최소 분할 + 철거 점 + 매 거 진)
주어진 무 방향 그림 에서 최소한 몇 개의 정점 을 제거 해 야 s 와 t 가 연결 되 지 않 습 니 다.
알고리즘:
s 와 t 가 직접 연결 되 어 no answer 를 출력 한다 고 가정 합 니 다.
각 점 을 두 개의 점 v 와 v '로 나 누 면 이 두 점 사이 에 하나의 가중치 가 1 인 변 (잔여 용량) 이 연 결 됩 니 다.
v 와 v 는 각각 하나의 흐름 점 이다.유출 점
최소 절단 의 성질 에 근거 하 다.가중치 가 작은 쪽 은 선택 할 수 있 습 니 다.
원점 st = 0 과 외환 점 en = 2 * n + 1 을 추가 하고 원점 과 s 의 연 권 치 는 inf 의 변 입 니 다.t '와 외환 점 의 연 권 치 는 inf 의 변 이다.
s 와 s', t 와 t '의 연 권 치 는 inf 의 변 으로 자신 과 자신 이 연락 을 잃 지 않도록 보장 합 니 다.
i 와 j 가 연결 되 어 있다 고 가정 하 세 요.i '와 j 의 연 권 치 는 inf 의 변 이다.j '와 i 의 연 권 치 는 inf 의 변 이다.
이렇게 그림 을 만 든 후에 가장 큰 흐름 을 달 려 서 구 하 는 유량 은 바로 점 의 개수 이다.
그리고 번 호 는 어 릴 때 부터 모든 점 을 매 거 했다.이 점 을 없 애 보 세 요.또 한 번 그림 을 세우 고 최대 흐름 을 달리다.
최대 흐름 이 줄 어 들 지.줄 었 다 고 가정 하면 빼 야 할 점 이다.기록 해서 마지막 출력 하면 돼.
PS:
건 도 는 원점 과 외환 점 을 추가 하지 않 고 바로 제거 하지 않 은 점 을 가 할 수 있다. 철거 한 두 점 은 직접 가중치 가 1 인 변 이 고 가장자리 가 연결 되 어 있다.
2 점 의 연 권 치 는 INF 의 변 이다.
결국 내 가 쓴 Dinic 템 플 릿 은 잔여 네트워크 즉 e [i]. val 을 직접 처리 해 왔 다 는 것 을 이해 했다.
용량 망 과 트 래 픽 을 분리 해서 쓴 다 이 닉 도 있다.
#include<cstdio>
#include<iostream>
#include<cstring>
#define INF 0x3f3f3f3f
#define maxn 210
#define maxm 160000
using namespace std;
struct node
{
int v,val,next;
}e[maxm<<1];
int head[maxn<<1],mp[maxn][maxn],cnt,st,en,s,t,n;
int d[maxn<<1],q[maxn<<1],mm[maxn],del[maxn];
void init()
{
memset(del,0,sizeof(del));
memset(mp,0,sizeof(mp));
st = 0;
en = 2*n+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
scanf("%d",&mp[i][j]);
}
}
void add(int x,int y,int z)
{
e[cnt].v = y;
e[cnt].val = z;
e[cnt].next = head[x];
head[x] = cnt++;
e[cnt].v = x;
e[cnt].val = 0;
e[cnt].next = head[y];
head[y] = cnt++;
}
void build()
{
memset(head,-1,sizeof(head));
cnt = 0;
add(st,s,INF);
add(t+n,en,INF);
for(int i=1;i<=n;i++)
{
if(!del[i]) add(i,i+n,1);
for(int j=1;j<=n;j++)
{
if(mp[i][j])
add(i+n,j,INF);
}
}
add(s,s+n,INF);
add(t,t+n,INF);
}
bool bfs()
{
memset(d,-1,sizeof(d));
int f = 0,r = 0,u;
q[r++] = st;
d[st] = 0;
while(f<r)
{
u = q[f++];
for(int i=head[u];i!=-1;i=e[i].next)
{
int t = e[i].v;
if(e[i].val>0 && d[t]==-1)//>0
{
d[t] = d[u]+1;
q[r++] = t;
if(t==en) return true;
}
}
}
return false;
}
int dfs(int x,int flow)
{
if(x==en) return flow;
int ret = 0,dd;
for(int i=head[x];ret<flow && i!=-1;i=e[i].next)
{
int t = e[i].v;
if(d[t] == d[x]+1 && e[i].val)
{
dd = dfs(t,min(flow,e[i].val));
e[i].val-=dd;
e[i^1].val+=dd;
flow-=dd;
ret+=dd;
}
}
if(!ret) d[x]=-1;
return ret;
}
int Dinic()
{
int tmp = 0,maxflow = 0;
while(bfs())
{
while(tmp=dfs(st,INF))
maxflow+=tmp;
}
return maxflow;
}
void solve()
{
if(mp[s][t])
{
printf("NO ANSWER!
");
return;
}
build();
int ans = Dinic();
printf("%d
",ans);
if(!ans) return;
int tmp = ans,f = 0,now;
for(int i=1;i<=n;i++)
{
if(i==s || i==t) continue;
//if(!mp[s][i]) continue; // i s 。 , continue
del[i] = 1;
build();
now = Dinic();
if(now<tmp)
{
mm[f++] = i;
tmp = now;
}
else
del[i] = 0;
}
for(int i=0;i<f-1;i++)
printf("%d ",mm[i]);
printf("%d
",mm[f-1]);
}
int main()
{
while(scanf("%d%d%d",&n,&s,&t)!=EOF)
{
init();
solve();
}
return 0;
}
/*
9 1 9
1 1 1 0 0 0 0 0 0
1 1 1 1 1 0 0 0 0
1 1 1 0 1 1 0 0 0
0 1 0 1 0 0 1 0 0
0 1 1 0 1 0 1 1 0
0 0 1 0 0 1 0 1 0
0 0 0 1 1 0 1 1 1
0 0 0 0 1 1 1 1 1
0 0 0 0 0 0 1 1 1
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.