bzoj2229 최소 분할 치료 & 네트워크 흐름
우선 두 개의 점을 선택하여 최소 베기 업데이트 답을 선택한 다음에 S와 연결된 것을 귀속시키고 T와 연결된 것을 귀속시키면 됩니다.하지만 증명은 안 해...
AC 코드는 다음과 같습니다.
#include<iostream>
#include<cstdio>
#include<cstring>
#define N 205
#define M 6005
using namespace std;
int n,m,tot,sta,gol,fst[N],cur[N],pnt[M],len[M],nxt[M],d[N],h[N],num[N],fa[N],a[N],b[N],c[N][N];
bool vis[N];
void add(int x,int y,int z){
pnt[++tot]=y; len[tot]=z; nxt[tot]=fst[x]; fst[x]=tot;
}
void bfs(){
memset(num,0,sizeof(num));
memset(d,0x3f,sizeof(d)); d[gol]=0;
int head=0,tail=1; h[1]=gol;
while (head<tail){
int x=h[++head],p; num[d[x]]++;
for (p=fst[x]; p; p=nxt[p]) if (len[p^1]){
int y=pnt[p];
if (d[x]+1<d[y]){
d[y]=d[x]+1; h[++tail]=y;
}
}
}
}
int up(){
int i,tmp=1000000000;
for (i=gol; i!=sta; i=pnt[fa[i]^1]) tmp=min(tmp,len[fa[i]]);
for (i=gol; i!=sta; i=pnt[fa[i]^1]){
len[fa[i]]-=tmp; len[fa[i]^1]+=tmp;
}
return tmp;
}
int isap(){
int i;
for (i=2; i<=tot; i++){ len[i]=len[i^1]=(len[i]+len[i^1])>>1; }
bfs(); memcpy(cur,fst,sizeof(fst));
int x=sta,flow=0,p; bool flag;
while (d[x]<n){
if (x==gol){ flow+=up(); x=sta; }
flag=1;
for (p=cur[x]; p; p=nxt[p]) if (len[p]){
int y=pnt[p];
if (d[y]+1==d[x]){
fa[y]=cur[x]=p; x=y;
flag=0; break;
}
}
if (flag){
int mn=n-1; cur[x]=fst[x];
for (p=fst[x]; p; p=nxt[p])
if (len[p]) mn=min(mn,d[pnt[p]]);
num[d[x]]--; if (!num[d[x]]) break;
d[x]=mn+1; num[d[x]]++;
if (x!=sta) x=pnt[fa[x]^1];
}
}
return flow;
}
void dfs(int x){
vis[x]=1; int p;
for (p=fst[x]; p; p=nxt[p]) if (len[p] && !vis[pnt[p]]) dfs(pnt[p]);
}
void solve(int l,int r){
if (l==r) return;
sta=a[l]; gol=a[r]; int flow=isap(),i,j;
memset(vis,0,sizeof(vis)); dfs(sta);
for (i=1; i<=n; i++) if (vis[i])
for (j=1; j<=n; j++) if (!vis[j])
c[j][i]=c[i][j]=min(c[i][j],flow);
int x=l,y=r;
for (i=l; i<=r; i++)
if (vis[a[i]]) b[x++]=a[i]; else b[y--]=a[i];
for (i=l; i<=r; i++) a[i]=b[i];
if (l<x) solve(l,x-1); if (y<r) solve(y+1,r);
}
int main(){
int cas; scanf("%d",&cas);
while (cas--){
scanf("%d%d",&n,&m); int i,x,y,z;
tot=1; memset(fst,0,sizeof(fst));
memset(c,0x3f,sizeof(c));
for (i=1; i<=m; i++){
scanf("%d%d%d",&x,&y,&z);
add(x,y,z); add(y,x,z);
}
for (i=1; i<=n; i++) a[i]=i; solve(1,n);
scanf("%d",&m);
while (m--){
int ans=0,j; scanf("%d",&x);
for (i=2; i<=n; i++)
for (j=1; j<i; j++) if (c[i][j]<=x) ans++;
printf("%d
",ans);
}
puts("");
}
return 0;
}
by lych
2016.4.15
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
DFS(깊이우선탐색), BFS(너비우선탐색)그래프와 트리 그래프(graph) 정점(node)과 그 정점을 연결하는 간선(edge)로 이루어진 자료구조의 일종 그래프를 탐색한다는 것은 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 트...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.