Gym - 101667E：How Many to Be Happy? (dinic 알고리즘 최소 화)
1659 단어 널빤지
제목: 무 방향 연결 도 를 지정 하여 H (e) 를 변 e 가 연 결 된 그림 의 최소 생 성 트 리 에 삭제 해 야 할 최소 변 수 를 포함 하도록 합 니 다.
사고: 최소 생 성 트 리 를 구성 하려 면 우 리 는 먼저 가장 작은 변 을 선택 한 다음 에 비교적 큰 변 을 선택해 야 한다. 이것 이 바로 최소 생 성 트 리 의 Kruskal 알고리즘 이다.그러면 e 가 u, v 두 점 을 연결 할 때 우 리 는 u 를 연결 해 야 한다. v 의 가장 짧 은 변 은 e 이다. 최소 생 성 트 리 에 e 를 포함 하 는 것 을 확보 할 수 있다. 그래서 우 리 는 e 의 두 점 을 원점 과 합류 점 으로 하고 최소 절단, 즉 H (e) 를 뛰 어 내 려 마지막 에 화 해 를 구하 면 된다.
【 코드 】
#include
using namespace std;
const int inf=0x3f3f3f3f;
const int N=105,M=1005;
int n,m,head[N],cnt;
int from[M],to[M],flow[M];
struct node{
int u,v,w;
}a[M];
void addedge(int u,int v,int f)
{
from[cnt]=head[u];
to[cnt]=v;
flow[cnt]=f;
head[u]=cnt++;
}
queue Q;
int level[N];
int bfs(int S,int T)
{
while(!Q.empty()) Q.pop();
memset(level,0,sizeof(level));
level[S]=1;
Q.push(S);
while(!Q.empty()){
int u=Q.front();
for(int i=head[u];i!=-1;i=from[i]){
int v=to[i];
if(!flow[i]||level[v]) continue;
level[v]=level[u]+1;
Q.push(v);
if(v==T) return 1;
}
Q.pop();
}
return 0;
}
int dfs(int u,int minf,int T)
{
if(u==T) return minf;
int res=0;
for(int i=head[u];i!=-1;i=from[i]){
int v=to[i];
if(level[v]!=level[u]+1||!flow[i]) continue;
int tmp=dfs(v,min(minf,flow[i]),T);
minf-=tmp,res+=tmp;
flow[i]-=tmp,flow[i^1]+=tmp;
if(minf==0) return res;
}
level[u]=0;
return res;
}
int dinic(int S,int T)
{
for(int i=0;i [문제 면]
How Many to Be Happy?
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Gym - 101667E：How Many to Be Happy? (dinic 알고리즘 최소 화)[문제 풀이] 제목: 무 방향 연결 도 를 지정 하여 H (e) 를 변 e 가 연 결 된 그림 의 최소 생 성 트 리 에 삭제 해 야 할 최소 변 수 를 포함 하도록 합 니 다. 사고: 최소 생 성 트 리 를 구성 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
