알고리즘 복습 - 오로라 회로 혼합 도 (bzoj 2095 2 분 + 네트워크 흐름)

제목:
Description
YYD 는 다이 어 트 를 위해 마른 바다 에 왔 다. 이 바 다 는 거대 한 바다 다. 바다 에는 n 개의 작은 섬 이 있 고 작은 섬 사이 에는 m 개의 다리 가 연결 되 어 있 으 며 두 개의 작은 섬 사이 에는 두 개의 다리 가 없 으 며 하나의 작은 섬 에서 다른 작은 섬 으로 갈 수 있다.현재 YYD 는 자전 거 를 타고 섬 1 에서 출발 해 다 리 를 건 너 섬 마다 도착 한 뒤 섬 1 로 돌아 가 고 싶 어 한다.패 중 학생 은 YYD 의 다이 어 트 를 성공 시 키 기 위해 큰 바람 을 불 렀 습 니 다. 바다 이기 때문에 바람 이 매우 세 졌 습 니 다. 모든 다 리 를 지나 면 바람 이 YYD 를 방해 할 수 밖 에 없 었 습 니 다. YYD 는 매우 dt 입 니 다. 그래서 슈크림 으로 당신 에 게 뇌물 을 주 었 습 니 다. 당신 이 그 에 게 감당 할 수 있 는 최대 풍력 이 가장 작은 노선 을 찾 아 주 었 으 면 합 니 다.
Input
입력: 첫 번 째 행위 두 개 는 빈 칸 으로 격 리 된 정수 n (2 < = n < = 1000), m (1 < = m < 2000) 을 읽 고 다음 에 m 행 이 빈 칸 으로 격 리 된 4 개의 정수 a, b (1 < = a, b < = n, a < b), c, d (1 < = c, d < 1000) 를 읽 으 면 i + 1 행 i 번 째 다 리 는 작은 섬 a 와 b 를 연결 하고 a 에서 b 까지 받 는 바람 은 c 이 며 b 에서 a 까지 받 는 바람 은 d 임 을 나타 낸다.
Output
출력: 다이어트 계획 을 완성 하지 못 하면 NIE 를 출력 합 니 다. 그렇지 않 으 면 첫 번 째 줄 의 출력 은 바람 의 최대 치 를 견 딜 수 있 습 니 다. (최소 화)
Sample Input
4 4 1 2 2 4 2 3 3 4 3 4 4 4 4 1 5 4
Sample Output
4
HINT
 
주의: 다 리 를 통 해 오로라 로 돌아 가기
문제 풀이:
  2 분 의 답 후의 그림 은 반드시 무 방향 변 + 단 방향 변 의 혼합 그림 이 고 혼합 그림 의 오로라 회 로 는 구체 적 인 구법 은 다음 과 같다.
  이 그림 의 무방 향 변 을 마음대로 방향 을 정 하고 각 점 의 입도 와 출 도 를 계산한다. 만약 어떤 점 의 출입 도의 차이 가 홀수 라면 오 라 회 로 는 존재 하지 않 을 것 이다. 오 라 회 로 는 매 점 의 입 도 를 요구 하기 때문이다. 즉, 총 도 수 는 짝수 이 므 로 홀수 점 이 존재 하면 오 라 회 로 가 있어 서 는 안 된다.
  자, 이제 각 점 의 입도 와 출도 의 차 이 는 모두 짝수 입 니 다. 그러면 이 짝수 를 2 로 나 누 면 x 를 얻 습 니 다. 즉, 각 점 에 대해 x 변 의 방향 을 바 꾸 면 (입 > 출 은 변 입, 입 > 입 은 변 출) 입 니 다. 각 점 이 출 = 입 이 라면 분명 합 니 다. 이 그림 은 오로라 회로 가 존재 합 니 다.
  현재 의 문 제 는 내 가 어떤 변 을 바 꿔 야 하 는 지, 모든 점 을 = 입? 구조 네트워크 흐름 모델 로 바 꿀 수 있 습 니 다.
  우선, 방향 이 있 으 면 방향 을 바 꿀 수 없습니다. 필요 하지 않 습 니 다. 삭제 하 십시오. 처음에는 방향 이 없 는 방향 을 정 하지 않 았 습 니까? 방향 을 정 하면 네트워크 를 어떻게 구축 합 니까? 변 용량 상한 선 1. 다른 s 와 t 를 새로 만 듭 니 다. 입 > 출 점 u 에 대해 서 는 연결 변 (u, t), 용량 은 x 입 니 다. 출 > 입 점 v 에 대해 서 는 연결 변 (s, v), 용량 은 x 입 니 다.  이후 S 에서 나 오 는 모든 변 이 만 류 했 는 지 살 펴 본다. 있 으 면 오 라 회 로 가 있 고 없 으 면 없다. 오 라 회 로 는 어느 것 일 까? 흐름 치 를 살 펴 보고 모든 유량 을 0 (상한 선 은 1, 흐름 치 는 0 이 아니면 1) 이 아 닌 변 을 반대로 돌리 면 매 점 의 입도 = 출 도의 오 라 도 를 얻 을 수 있다.   만 류 이기 때문에 모든 입 > 출 점 에 x 개의 변 이 들 어 옵 니 다. 이 들 어 오 는 변 을 반대로, OK, 입 = 출. 출 > 입 점 에 대해 서도 마찬가지 입 니 다. 그러면 s, t 와 연결 되 지 않 은 점 은 어떻게 합 니까? s 와 연결 하 는 조건 은 출 > 입, t 와 연결 하 는 조건 은 입 > 출 입 니 다. 그러면 이것 은 s 도 t 와 연결 되 지 않 은 점 입 니 다. 자 연 스 럽 게 처음부터 만족 하 게 되 었 습 니 다 =나 왔 습 니 다. 그러면 네트워크 흐름 과정 에서 이런 점 들 은 '중간 점' 에 속 합 니 다. 우 리 는 중간 점 의 유량 이 누적 되 는 것 을 허락 하지 않 는 다 는 것 을 알 고 있 습 니 다. 그러면 들 어 가 는 만큼 나 오고 반대로 돌아 간 후에 도 자 연 스 럽 게 균형 을 유지 합 니 다.   그래서 이렇게 투 오 라 회 로 문 제 를 혼합 해 풀 었 다.
코드:
  md 변 의 수량 이 0 으로 초기 화 되 어 어디 가 틀 렸 는 지 확인 되 지 않 았 습 니 다.
  

#include
#include
#include
#include
#include
#include
#include
#include<string>
#include
using namespace std;
const int N=1005;
const int M=4005;
struct node
{
  int from,go;
  int val1,val2;
}edge[M];
int n,m,tot,father[N],size[N],chu[N],ru[N],src,des,maxx,temp;
int first[N],go[M*2],next[M*2],rest[M*2],lev[N],cur[N],totl;
inline int getfa(int a)
{
  if(father[a]==a)  return a;
  father[a]=getfa(father[a]);
  return father[a];
}
inline void combfa(int a,int b)
{
  int fa=getfa(a);
  int fb=getfa(b);
  if(fa!=fb)
    father[fa]=fb,size[fb]+=size[fa];
}
inline void comb(int a,int b,int c)
{
  next[++totl]=first[a],first[a]=totl,go[totl]=b,rest[totl]=c;
  next[++totl]=first[b],first[b]=totl,go[totl]=a,rest[totl]=0;
}
inline bool bfs()
{
  for(int i=src;i<=des;i++)  cur[i]=first[i],lev[i]=-1;
  static int que[N],tail,u,v;
  que[tail=1]=src;
  lev[src]=0;
  for(int head=1;head<=tail;head++)
  {
    u=que[head];
    for(int e=first[u];e;e=next[e])
    {
      if(lev[v=go[e]]==-1&&rest[e])
      {
        lev[v]=lev[u]+1;
        que[++tail]=v;
        if(v==des)  return true;
      }
    }
  }
  return false;
}
inline int dinic(int u,int flow)
{
  if(u==des)
    return flow;
  int res=0,delta,v;
  for(int &e=cur[u];e;e=next[e])
  {
    if(lev[v=go[e]]>lev[u]&&rest[e])
    {
      delta=dinic(v,min(flow-res,rest[e]));
      if(delta)
      {
        rest[e]-=delta;
        rest[e^1]+=delta;
        res+=delta;
        if(res==flow)  break;
      }
    }
  }
  if(flow!=res)  lev[u]=-1;
  return res;
}
inline void maxflow()
{
  while(bfs())
    temp+=dinic(src,100000000);
}
inline bool check(int limit)
{
  memset(chu,0,sizeof(chu));
  memset(ru,0,sizeof(ru));
  memset(first,0,sizeof(first));
  src=0,des=n+1,maxx=0,temp=0,totl=1;
  for(int i=1;i<=n;i++)
    father[i]=i,size[i]=1;
  for(int i=1;i<=m;i++)
  {
    if(edge[i].val1<=limit&&edge[i].val2<=limit)//      
    {  
      comb(edge[i].from,edge[i].go,1); 
      chu[edge[i].from]++;
      ru[edge[i].go]++;
      combfa(edge[i].go,edge[i].from);
     }
    else
      if(edge[i].val1<=limit)
      {
        chu[edge[i].from]++;
        ru[edge[i].go]++;
        combfa(edge[i].from,edge[i].go); 
       }
      else
        if(edge[i].val2<=limit)
        { 
          chu[edge[i].go]++;
          ru[edge[i].from]++;
          combfa(edge[i].from,edge[i].go);
        }
        else return false;
  }
  if(size[getfa(1)]!=n)  return false;
  for(int i=1;i<=n;i++)
  { 
    if(chu[i]==ru[i])  continue;
    if(ru[i]<chu[i])
    {
      if((chu[i]-ru[i])%2==1)  return false;
      else  comb(src,i,(chu[i]-ru[i])/2),maxx+=((chu[i]-ru[i])/2);
    }
    else
    {
      if((ru[i]-chu[i])%2==1)  return false;
      else comb(i,des,(ru[i]-chu[i])/2);
    }
  }
  maxflow();
  if(temp!=maxx)  return false;
  else return true;
}
inline bool cmp(node a,node b)
{
  return a.val1<b.val1;
}
int main()
{
  //freopen("a.in","r",stdin);
  scanf("%d%d",&n,&m);
  int a,b,c,d,ans=0;
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d%d%d",&a,&b,&c,&d);
    edge[i].from=a;
    edge[i].go=b;
    edge[i].val1=c;
    edge[i].val2=d;
  }
  int left=1,right=1000;
  while(left<=right) 
  {
    int mid=(left+right)/2;
    if(check(mid))  right=mid-1,ans=mid;
    else left=mid+1;
  }
  if(!ans)  cout<<"NIE"<<endl;
  else cout<endl;
  return 0;
}

 
다음으로 전송:https://www.cnblogs.com/AseanA/p/7472389.html