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

(追記) (追記ここまで)

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

1489번 - 대결

smu201111192 8년 전 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 8년 전 1

5 4 3 2

4 3 2 1

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

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

smu201111192 8년 전 0

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

감사합니다. 구사과님!

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

(追記) (追記ここまで)

Baekjoon Online Judge

채점 현황

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말

사업자 등록 번호: 541-88-00682
대표자명: 최백준
주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
전화번호: 02-521-0487 (이메일로 연락 주세요)
이메일: contacts@startlink.io
통신판매신고번호: 제 2017-서울서초-2193 호

한국어 | English (Beta)

문제

문제

출처

ICPC

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

smu201111192 8년 전 0

koosaga 8년 전 1

smu201111192 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말