HDU 4685 다이어그램 일치 + tarjan
대체로
n명의 왕자와 m명의 공주가 있어요.
모든 왕자는 몇 명의 공주를 좋아한다. 즉, 왕자는 자신이 좋아하는 공주와만 결혼한다.
공주는 비교적 비참해서 누구와 결혼해도 된다
그리고 왕자의 가능한 결혼 상대를 출력합니다.
왕자와 임의의 이들 대상 중의 한 사람이 결혼하더라도 남은 왕자의 짝수에 영향을 주지 않을 것을 보증해야 한다. 즉, 남은 왕자 중 갑자기 한 사람이 결혼할 수 없게 해서는 안 된다.
그리고 사고방식은 사실 POJ1904와 매우 비슷하다.
하지만 POJ 문제는 초기의 완비된 일치성을 제시했다.
본제는 없다
어쩌면 좋아
우리는 온갖 방법을 다 강구하여 완비된 일치성을 만들어야 한다
처음에 저희가 이분도를 한번 만들어서 최대한 일치시킬 수 있어요.
그러면 양쪽 인원이 같지 않기 때문에 솔로가 될 수도 있어요.
그럼 이쯤에서 우리는 이 솔로들에게 상대를 정해야 한다.
안배된 대상이 이미 있는 이 사람들 중 누구도 될 수 없다면, 어쩔 수 없이 몇 사람을 더 가상해서 나올 수밖에 없다.
"이 사람들은 컵을 비교하는구나, 대상은 모두 가상이다."
왕자에게 남은 것이 있다고 가정하면 남은 왕자마다 가상의 공주가 하나씩 있는데, 이 공주는 모든 왕자에게 사랑받는다.
만약에 공주에게 남은 것이 있다면 남은 공주마다 가상의 왕자가 하나 있을 것이다. 이 왕자는 모든 공주를 좋아한다.
그리고 완비 매칭으로 구성됐습니다.다음 단계는 1904랑 만져볼게요.
코드를 넣었으니 입력 최적화를 더하면 비교적 시원하다.잘못되면독자가 지적해 주십시오.
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <string>
#include <cstring>
#include <cmath>
#define MAXN 2005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct Edge
{
int v, next;
}edge[200 * MAXN], newedge[255555];
int head[MAXN], e, visited[MAXN], newhead[MAXN], newe;
int top, scc, index;
int low[MAXN], dfn[MAXN], instack[MAXN];
int order[MAXN], cnt, st[MAXN], fa[MAXN];
int mark[MAXN], cx[MAXN], cy[MAXN];
int n, m;
int nt, all;
void init()
{
top = scc = index = e = 0;
memset(head, -1, sizeof(head));
memset(dfn, 0, sizeof(dfn));
memset(instack, 0, sizeof(instack));
memset(newhead, -1, sizeof(newhead));
newe = 0;
}
inline void insert(const int &x, const int &y)
{
edge[e].v = y;
edge[e].next = head[x];
head[x] = e++;
}
inline int in()
{
char ch;
int a = 0;
while((ch = getchar()) == ' ' || ch == '
');
a += ch - '0';
while((ch = getchar()) != ' ' && ch != '
')
{
a *= 10;
a += ch - '0';
}
return a;
}
inline void out(int a)
{
if(a >= 10)out(a / 10);
putchar(a % 10 + '0');
}
inline void newinsert(const int &x, const int &y)
{
newedge[newe].v = y;
newedge[newe].next = newhead[x];
newhead[x] = newe++;
}
inline int path(int u)
{
for(int i = newhead[u]; i != -1; i = newedge[i].next)
{
int v = newedge[i].v;
if(!mark[v])
{
mark[v] = 1;
if(cy[v] == -1 || path(cy[v]))
{
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int solve()
{
int ans = 0;
memset(cx, -1, sizeof(cx));
memset(cy, -1, sizeof(cy));
for(int i = 1; i <= nt; i++)
{
memset(mark, 0, sizeof(mark));
ans += path(i);
}
return ans;
}
void readdata()
{
int t, v;
for(int i = 1; i <= n; i++)
{
t = in();
while(t--)
{
v = in();
insert(i, v + nt);
newinsert(i, v + nt);
}
}
solve();
all = 2 * nt;
for(int i = 1; i <= nt; i++)
if(cx[i] == -1)
{
++all;
cx[i] = all;
cy[all] = i;
for(int k = 1; k <= nt; k++)
insert(k, all);
}
for(int j = 1; j <= nt; j++)
if(cy[j + nt] == -1)
{
++all;
cy[j + nt] = all;
cx[all] = j + nt;
for(int k = 1; k <= nt; k++)
insert(all, k + nt);
}
for(int i = 1; i <= all; i++)
if(cx[i] != -1)
insert(cx[i], i);
}
void tarjan(int u)
{
low[u] = dfn[u] = ++index;
instack[u] = 1;
st[++top] = u;
int v;
for(int i = head[u]; i != -1; i = edge[i].next)
{
v = edge[i].v;
if(!dfn[v])
{
tarjan(v);
low[u] = min(low[u], low[v]);
}
else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u])
{
scc++;
do
{
v = st[top--];
instack[v] = 0;
fa[v] = scc;
}while(v != u);
}
}
void gao()
{
init();
readdata();
for(int i = 1; i <= all; i++)
if(!dfn[i]) tarjan(i);
for(int u = 1; u <= n; u++)
{
cnt = 0;
int ans[MAXN];
for(int i = head[u]; i != -1; i = edge[i].next)
{
int v = edge[i].v;
if(fa[u] == fa[v])
{
if(v - nt <= m)
ans[cnt++] = v - nt;
}
}
sort(ans, ans + cnt);
out(cnt);
for(int i = 0; i < cnt; i++)
{
putchar(' ');
out(ans[i]);
}
puts("");
}
}
int main()
{
int cas = 0;
int T;
//freopen("C:/in.txt", "r", stdin);
//freopen("C:/out2.txt", "w", stdout);
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &n, &m);
nt = max(n, m);
printf("Case #%d:
", ++cas);
gao();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.