poj 3155 (최대 밀도 서브 맵)
사고: 후진 타 오의 논문 은 두 가지 방법 을 소개 했다.
첫 번 째: 최대 권 폐쇄 도 모델 로 전환 하여 설명 한다.
max g = f (x) = | E '| / V' | 를 설정 합 니 다. 하위 그림 의 변수 와 포인트 의 비율 이 그 중에서 가장 큽 니 다. 우 리 는 보통 함수 max h (g) = | E '| - g * V' | 를 구성 합 니 다. h (g) 가 0 일 때 g 의 값 이 가장 좋 습 니 다. h (g) > 0 일 때 g < 최 우수 치, h (g) < 0 일 때 g > 최 우수 치 입 니 다.최대 치가 0 보다 크 면 우 리 는 g 의 값 을 계속 증가 시 켜 h (g) 를 줄 일 수 있 기 때 문 입 니 다. 만약 에 최대 치가 0 보다 작 으 면 g 는 증가 할 수 없고 감소 할 수 있 습 니 다!
h (g) 를 관찰 하면 변 과 점 이 의존 관계 가 있 으 면 변 의존 점, 변 에 존재 하 는 필요 한 조건 은 점 의 존재 이다. 그러면 앞으로 우리 가 변 을 점 으로 본다 면 이것 은 가장 큰 권 폐 합 자 도 에 부합 되 지 않 을 것 이다.현재 h (g) 의 구법 은 새로운 그림 의 최대 권 폐 합 자 그림 의 값 을 구 하 는 것 을 통 해 해결 할 수 있 습 니 다. 그러나 여기 문제 가 있 습 니 다. 그림 을 만 든 후에 구 하 는 값 과 h (g) 가 원래 값 에 대응 하지 않 아야 한 다 는 것 을 알 수 있 습 니 다. (구체 적 으로 왜 이해 하지 못 하 는 지) 이렇게 이해 할 수 있 습 니 다. 가장 작은 g 이 h (g) 를 0 으로 만 들 때 가장 좋 은 것 으로 풀 어야 합 니 다. 왜냐하면 h (g)단조 로 운 체감 함수 입 니 다. 이 함수 로 볼 때 하나의 g 만 존재 할 수 있 습 니 다. h (g) = 0;그러나 최대 권 폐 합 자 도 를 구 하 는 것 은 서브 맵 의 가중치 와 0 이 많은 중 g 입 니 다. 가장 작은 g 으로 h (g) 를 0 으로 만 든 후에 g 가 계속 커지 면 최대 권 폐 합 자 도 를 통 해 구 하 는 값 은 0 이지 만 진정한 h (g) < 0 이기 때문에 가장 좋 은 해 를 얻 으 려 면 가장 큰 권 폐 합 자 도 를 만 드 는 가중치 와 0 의 가장 작은 g 값 입 니 다!이렇게 구 해 를 한 후에 원점 에서 합류 점 으로 흐 르 는 변 은 바로 최대 밀도 서브 맵 중의 점 이다.
두 번 째:
원점 에서 각 점 까지 연결 하 는 것 은 방향 변 의 가중치 가 U 이 고 각 점 에서 외환 점 까지 연결 하 는 변 의 가중치 가 U + 2 * g - d 이 며 원래 관계 가 있 는 점 연결 두 개 는 방향 변 (u, v) 이 있 으 며 (v, u) 의 가중치 가 1 (U 는 m 를 취 할 수 있 고 U 의 목적 은 2 * g - d 의 값 을 항상 플러스 로 하 는 것) 이다. 이런 다음 에 최소 로 자 르 면 h (g) = (U * n - mincut) / 2;2 점 에서 가장 좋 은 값 을 찾 으 면 mid 이지 만 그림 의 점 을 요구 하면 left 로 새 그림 에서 최대 흐름 을 구 한 다음 에 원점 에서 dfs 를 옮 겨 다 니 며 결 과 를 얻어 야 합 니 다.
첫 번 째 코드:
#include<stdio.h>
#include<string.h>
const int N=1500;
const double inf=0x3fffffff;
const double eps=1e-8;
int gap[N],dis[N],start,end,ans,sum,head[N],num,dep[N],n,m;
bool vis[N];
struct edge
{
int st,ed,next;
double flow;
}e[80*N];
struct node
{
int x,y;
}P[1100];
void addedge(int x,int y,double w)
{
e[num].st=x;e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;
e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;
}
void makemap(double g)
{
int i;
memset(head,-1,sizeof(head));
num=0;
for(i=1;i<=n;i++)
addedge(i,end,g);
for(i=0;i<m;i++)
{
addedge(n+i+1,P[i].y,inf);
addedge(n+i+1,P[i].x,inf);
addedge(start,n+i+1,1.0);
}
}
double dfs(int u,double minflow)
{
if(u==end)return minflow;
int i,v;
double f,flow=0.0;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(e[i].flow>0)
{
if(dis[v]+1==dis[u])
{
f=dfs(v,e[i].flow>minflow-flow?minflow-flow:e[i].flow);
flow+=f;
e[i].flow-=f;
e[i^1].flow+=f;
if(minflow-flow<=1e-8)return flow;
if(dis[start]>=ans)return flow;
}
}
}
if(--gap[dis[u]]==0)
dis[start]=ans;
dis[u]++;
gap[dis[u]]++;
return flow;
}
double isap()
{
double maxflow=0.0;
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
gap[0]=ans;
while(dis[start]<ans)
maxflow+=dfs(start,inf);
return 1.0*m-maxflow;
}
void dfs1(int u)
{
vis[u]=true;
if(u>=1&&u<=n)
sum++;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].ed;
if(vis[v]==false&&e[i].flow>0)
dfs1(v);
}
}
int main()
{
int i;
double Left,Right,mid,flow;
while(scanf("%d%d",&n,&m)!=-1)
{
if(m==0){printf("1
1
");continue;}
start=0,end=n+m+1,ans=end+1;
for(i=0;i<m;i++)
{
scanf("%d%d",&P[i].x,&P[i].y);
}
Left=0;Right=m;
while(Right-Left>=1.0/n/n)// , 1/(n*n）
{
mid=(Left+Right)/2;
makemap(mid);
flow=isap();//
if(flow<eps)// 0，g
Right=mid;
else Left=mid;
}
makemap(Left);//
isap();
memset(vis,false,sizeof(vis));
sum=0;
dfs1(start);
printf("%d
",sum);
for(i=1;i<=n;i++)
if(vis[i]==true)//
printf("%d
",i);
}
return 0;
}두 번 째 코드:
#include<stdio.h>
#include<string.h>
const int N=110;
const double inf=0x3fffffff;
const double eps=1e-8;
int gap[N],dis[N],start,end,ans,sum,head[N],num,dep[N],n,m;
bool vis[N];
struct edge
{
int st,ed,next;
double flow;
}e[80*N];
struct node
{
int x,y;
}P[1100];
void addedge(int x,int y,double w)
{
e[num].st=x;e[num].ed=y;e[num].flow=w;e[num].next=head[x];head[x]=num++;
e[num].st=y;e[num].ed=x;e[num].flow=0;e[num].next=head[y];head[y]=num++;
}
void makemap(double g)
{
int i;
memset(head,-1,sizeof(head));
num=0;
for(i=1;i<=n;i++)
{
addedge(start,i,m*1.0);
addedge(i,end,m+2*g-dep[i]);
}
for(i=0;i<m;i++)
{
addedge(P[i].x,P[i].y,1.0);
addedge(P[i].y,P[i].x,1.0);
}
}
double dfs(int u,double minflow)
{
if(u==end)return minflow;
int i,v;
double f,flow=0.0;
for(i=head[u];i!=-1;i=e[i].next)
{
v=e[i].ed;
if(e[i].flow>0)
{
if(dis[v]+1==dis[u])
{
f=dfs(v,e[i].flow>minflow-flow?minflow-flow:e[i].flow);
flow+=f;
e[i].flow-=f;
e[i^1].flow+=f;
if(minflow-flow<=1e-8)return flow;
if(dis[start]>=ans)return flow;
}
}
}
if(--gap[dis[u]]==0)
dis[start]=ans;
dis[u]++;
gap[dis[u]]++;
return flow;
}
double isap()
{
double maxflow=0.0;
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
gap[0]=ans;
while(dis[start]<ans)
maxflow+=dfs(start,inf);
return maxflow;
}
void dfs1(int u)//
{
vis[u]=true;
sum++;
for(int i=head[u];i!=-1;i=e[i].next)
{
int v=e[i].ed;
if(vis[v]==false&&e[i].flow>0)
dfs1(v);
}
}
int main()
{
int i;
double Left,Right,mid,hg;
while(scanf("%d%d",&n,&m)!=-1)
{
if(m==0){printf("1
1
");continue;}
start=0,end=n+1,ans=end+1;
memset(dep,0,sizeof(dep));
for(i=0;i<m;i++)
{
scanf("%d%d",&P[i].x,&P[i].y);
dep[P[i].x]++;dep[P[i].y]++;
}
Left=0;Right=m;
while(Right-Left>=1.0/n/n)// , 1/(n*n）
{
mid=(Left+Right)/2;
makemap(mid);
hg=isap();
hg=(1.0*n*m-hg)/2;
if(hg>eps)
Left=mid;
else Right=mid;
}
makemap(Left);// mid wa, mid h(mid)>eps, Left
isap();
memset(vis,false,sizeof(vis));
sum=0;
dfs1(0);
printf("%d
",sum-1);
for(i=1;i<=n;i++)
if(vis[i]==true)
printf("%d
",i);
}
return 0;
}이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Linux Shell 프로 그래 밍 - 텍스트 처리 grep, sed사용자 가 지정 한 '모드' 에 따라 대상 텍스트 를 일치 하 게 검사 하고 일치 하 는 줄 을 인쇄 합 니 다. ##포함 되 지 않 음, 역방향 일치 \ ##키워드 앞 뒤 가 맞지 않 고 키워드 만 일치 합 니 다...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
