写作网站一稿多投的后果,app外包网,深圳网站设计师培训学校,东营会计信息网官网题目链接#xff1a;https://vjudge.net/problem/UVALive-3989 题解#xff1a; 题意#xff1a;有n个男生和n个女生。每个女生对男神都有个好感度排行#xff0c;同时每个男生对每个女生也有一个好感度排行。问#xff1a;怎样配对#xff0c;才能使的每个女生尽可能幸福… 题目链接https://vjudge.net/problem/UVALive-3989 题解 题意有n个男生和n个女生。每个女生对男神都有个好感度排行同时每个男生对每个女生也有一个好感度排行。问怎样配对才能使的每个女生尽可能幸福。规定在配对的过程中如果一对男女不是舞伴且他们喜欢对方的程度都大于当前的舞伴那么他么会“私奔”留下他们的舞伴孤零零。由于是要每个女生尽可能幸福所以女生根据喜欢程度主动去男生。而男生只能处于被动的状态。 代码如下 1 #include bits/stdc.h2 using namespace std;3 typedef long long LL;4 const int INF 2e9;5 const LL LNF 9e18;6 const int mod 1e97;7 const int MAXN 1e310;8 9 int pref[MAXN][MAXN], order[MAXN][MAXN], Next[MAXN];
10 int future_husband[MAXN], future_wife[MAXN];
11 queueintq;
12
13 void engage(int woman, int man)
14 {
15 int w future_wife[man];
16 if(w)
17 {
18 future_husband[w] 0;
19 q.push(w);
20 }
21 future_wife[man] woman;
22 future_husband[woman] man;
23 }
24
25 int main()
26 {
27 int T, n;
28 scanf(%d, T);
29 while(T--)
30 {
31 scanf(%d, n);
32 for(int i 1; in; i)
33 {
34 for(int j 1; jn; j)
35 scanf(%d, pref[i][j]);
36 Next[i] 1;
37 future_husband[i] 0;
38 q.push(i);
39 }
40
41 for(int i 1; in; i)
42 {
43 for(int j 1; jn; j)
44 {
45 int x;
46 scanf(%d, x);
47 order[i][x] j;
48 }
49 future_wife[i] 0;
50 }
51
52 while(!q.empty())
53 {
54 int woman q.front(); q.pop();
55 int man pref[woman][Next[woman]];
56 if(!future_wife[man])
57 engage(woman, man);
58 else if(order[man][woman]order[man][future_wife[man]])
59 engage(woman, man);
60 else q.push(woman);
61 }
62 while(!q.empty()) q.pop();
63
64 for(int i 1; in; i)
65 printf(%d\n, future_husband[i]);
66 if(T) printf(\n);
67 }
68 } View Code 转载于:https://www.cnblogs.com/DOLFAMINGO/p/7832143.html
