글 읽기 - ac를 받긴했는데 두 코드의 차이점을 잘 모르겠습니다.

smu201111192 7년 전 0

MCMF로 그대르 모델링을 해서 ac를 받았습니다.

그래프 모델링한걸 간단히 설명해드리자면

1.상대팀을 이길 수 있다면 cap=1,cost=-2 (2점을 얻을 수 있음)

2.비기는 경우라면 cap=1,cost=-1 (1점을 얻을 수 있음)

3.지는 경우라면 cap=1,cost=0 (0점을 얻을 수 있음)

이렇게 모델링하고 ac를 받았습니다.

그런데 3번의 경우는 굳이 고려를 안 해줘도 되지않을까요?(얻을 수 있는 점수가 전체 점수에 영향을 안 줄거 같습니다.)

도움 부탁드립니다!.

#include <iostream>
#include <cstdio>
#include <string>
#include <cassert>
#include <algorithm>
#include <set>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <cstring>
using namespace std;
struct edge{int to,cap,cost,rev;};
int INF=1e9;
int n;
const int MAX_V=3002;
vector<edge> G[MAX_V];
int dist[MAX_V];
int prevv[MAX_V],preve[MAX_V];
int inq[MAX_V]={0,};
void addEdge(int from,int to,int cap,int cost){
    G[from].push_back({to,cap,cost,(int)G[to].size()});
    G[to].push_back({from,0,-cost,(int)G[from].size()-1});
}
pair<int,int> min_cost_flow(int s,int t){
    int res=0;
    int total=0;
    queue<int> q;
    while(true){
        for(int i=0;i<MAX_V;i++)dist[i]=INF;
        dist[s]=0;
        q.push(s);
        inq[s]=1;
        while(!q.empty()){
            int here=q.front();
            q.pop();
            inq[here]=0;
            for(int i=0;i<G[here].size();i++){
                edge &e=G[here][i];
                if(e.cap>0 && dist[e.to]>dist[here]+e.cost){
                    dist[e.to]=dist[here]+e.cost;
                    prevv[e.to]=here;
                    preve[e.to]=i;
                    if(!inq[e.to]){
                        q.push(e.to);
                        inq[e.to]=1;
                    }
                }
            }
        }
        if(dist[t]>=1e9){
            return {total,res};
        }
        int d=1e9;
        for(int v=t;v!=s;v=prevv[v]){
            d=min(d,G[prevv[v]][preve[v]].cap);
        }
        res+=d*dist[t];
        total+=d;
        for(int v=t;v!=s;v=prevv[v]){
            edge&e=G[prevv[v]][preve[v]];
            e.cap-=d;
            G[v][e.rev].cap+=d;
        }
    }
    return {total,res};
}

int main(){
    ios::sync_with_stdio(false);
    int source=0;
    int sink=2005;
    int a[1001],b[1001];
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    for(int i=1;i<=n;i++){
        addEdge(source,i,1,0);
        addEdge(i+n,sink,1,0);
        for(int j=1;j<=n;j++){
            if(a[i]>b[j]){addEdge(i,j+n,1,-2); } //이길 수 있는 상대라면 2점
            else if(a[i]==b[j]){addEdge(i,j+n,1,-1);} //비기는 경우면 1점
            else addEdge(i,j+n,1,0); //그외의 경우는 0점....문제가 생긴부분
        }
    }
    auto node=min_cost_flow(source,sink);
    cout<<-node.second;
    return 0;
}

koosaga 7년 전 1

5 4 3 2

4 3 2 1

왜 문제가 되는지는 혼자 생각해보세요.

코스트가 0이라는 이유로 모델링한 그래프를 마음대로 바꾸지 마세요!

smu201111192 7년 전 0

아... maxflow가 안 만들어 질 수가 있군요!

감사합니다. 구사과님!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

ac를 받긴했는데 두 코드의 차이점을 잘 모르겠습니다.

smu201111192 7년 전 0

koosaga 7년 전 1

smu201111192 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말