저도 참고해서 풀었는데 시간초과 나더군요 ㅠㅠ
23번째 줄 인접리스트 벡터로 구현하셔서 간선 없는 부분 빼면 좀 빠르게 나와요
11376번 - 열혈강호 2
#include <bits/stdc++.h>
using namespace std;
#define in cin
#define out cout
#define REP(i,n) for(int i=0; i<n; i++)
#define REP2(i,s,e) for(int i=s; i<e; i++)
#define REPE(i,s,e) for(int i=s; i<=e; i++)
#define REPR(i,s,e) for(int i=s; i>=e; i--)
#define all(v) v.begin(), v.end()
#define pb push_back
#define ll long long
#define pii pair<int, int>
#define X first
#define Y second
#define intINF 2147483647
#define llINF 9223372036854775807LL
#define MOD 1000000007
#define rd(n) scanf("%d", &n)
#define rdll(n) scanf("%lld", &n)
const int MAX_V = 2010;
const int INF = intINF;
class flowNetwork
{
private:
int V;
int cap[MAX_V][MAX_V];
int flow[MAX_V][MAX_V];
vector<int> adj[MAX_V];
public:
void init(int n)
{
memset(cap, 0, sizeof(cap));
V = n;
}
void addEdge(int x, int y, int c)
{
cap[x][y] += c;
adj[x].push_back(y);
adj[y].push_back(x);
}
int get(int src, int sink)
{
memset(flow, 0, sizeof(flow));
int totalFlow = 0;
while(true)
{
int parent[MAX_V];
memset(parent, -1, sizeof(parent));
queue<int> Q;
parent[src] = src;
Q.push(src);
while(Q.size() && parent[sink] == -1)
{
int here = Q.front(); Q.pop();
for(int i = 0; i < adj[here].size(); i++)
{
int there = adj[here][i];
if(cap[here][there] - flow[here][there] > 0 &&
parent[there] == -1)
{
Q.push(there);
parent[there] = here;
}
}
}
if(parent[sink] == -1) break;
int amount = INF;
for(int p = sink; p != src; p = parent[p])
{
amount = min(amount,
cap[parent[p]][p] - flow[parent[p]][p]);
}
for(int p = sink; p != src; p = parent[p])
{
flow[parent[p]][p] += amount;
flow[p][parent[p]] -= amount;
}
totalFlow += amount;
}
return totalFlow;
}
};
int main()
{
int n, m; rd(n); rd(m);
// 0 : src
// 1~n
// n+1 ~ n+m
// n+m+1 sink
flowNetwork G;
G.init(n+m+10);
REPE(i, 1, n)
{
G.addEdge(0, i, 2);
}
REPE(i, 1, m)
{
G.addEdge(n+i, n+m+1, 1);
}
REPE(i, 1, n)
{
int k; rd(k);
REP(j, k)
{
int x; rd(x);
G.addEdge(i, n+x, 1);
}
}
printf("%d", G.get(0, n+m+1));
return 0;
}
저랑 다른게 없는거 같은데..
댓글을 작성하려면 로그인해야 합니다.
zipbob 7년 전
종만북을 보면서 네트워크 플로우에 대해 공부중입니다.
열혈강호1문제같은 경우는 이분매칭으로 해결하였지만
열혈강호2 문제는 한 사람이 2가지 일을 할 수 있어서
포드 폴커슨으로 해결하려고 하였습니다.
source는 0
사람 1~n
일 n+1~n+m
sink n+m+1
source -사람 2
사람-일 1
일-sink 1
로 가중치를 두고 구현해보았는데 시간초과뜨네요 무슨 문제인가요 ? 잘못된 부분이나 더 좋은 알고리즘 있으면 알려주시면 감사하겠습니다.
코드는 종만북 참고하였습니다.