算法期考题

1.The Stable Matching/Marriage Problem

Description

The Stable Matching/Marriage Problem states that given N men and N women, where each person has ranked all members of the opposite sex in order of preference, marry the men and women together such that there are no two people of opposite sex who would both rather have each other than their current partners. If there are no such people, all the marriages are “stable”

Input

the input contains 1+2N Lines,for example:

2 11 00 10 10 1

the first line has two numbers,the first number N means we have N men and N women to match,the second number K( 0 N >> K;

    vector men(N);

    vector women(N);

    for (int i = 0; i

        men[i].id = i;

        men[i].priorityList.resize(N);

        for (int j = 0; j

            cin >> men[i].priorityList[j];

        }

    }

    for (int i = 0; i

        women[i].id = i;

        women[i].priorityList.resize(N);

        for (int j = 0; j

            cin >> women[i].priorityList[j];

        }

        women[i].currentPartner = -1;

    }

    vector menEngaged(N, false);

    vector womenEngaged(N, -1);

    int engagedCount = 0;

    while (engagedCount

        int manId = -1;

        for (int i = 0; i

            if (!menEngaged[i]) {

                manId = i;

                break;

            }

        }

        for (int i = 0; i

            int womanId = men[manId].priorityList[i];

            if (womenEngaged[womanId] == -1) {

                womenEngaged[womanId] = manId;

                menEngaged[manId] = true;

                engagedCount++;

            } else {

                int currentManId = womenEngaged[womanId];

                int currentManPriority = std::find(women[womanId].priorityList.begin(),

                                                   women[womanId].priorityList.end(),

                                                   currentManId) - women[womanId].priorityList.begin();

                int newManPriority = std::find(women[womanId].priorityList.begin(),

                                               women[womanId].priorityList.end(),

                                               manId) - women[womanId].priorityList.begin();

                if (newManPriority

                    womenEngaged[womanId] = manId;

                    menEngaged[manId] = true;

                    menEngaged[currentManId] = false;

                }

            }

        }

    }

     for(int i=0;i>w;

      edges.push_back({u,v,w});

    }

    int ans=klskr();

    if(ans==-1){

        cout> num;

        pq.push(num);

    }

    int cost = 0;

    while (pq.size() > 1) {

        int a = pq.top();

        pq.pop();

        int b = pq.top();

        pq.pop();

        int sum = a + b;

        cost += sum;

        pq.push(sum);

    }

    cout n>>m;

    int sta,end;

    cin>>sta>>end;

     for (int i = 0; i

        for (int j = 0; j

            f[i][j] = 1e9;

        }

        f[i][i] = 0;

    }

    for(int i=0;i>a>>b>>c;

        f[a][b]=c;

    }

    for(int k=0;k{1, 0}, {-1, 0}, {0, 1}, {0, -1}}; queue> m; vector maze(n, vector(m)); for (int i = 0; i > maze[i][j]; } } int result = minMoves(maze); cout left, right->right) && isequal(left->right, right->left);}}int main() {vector nums;int num;while (cin>>num) {nums.push_back(num);}int n = nums.size();vector nodes(n,NULL);for (int i = 0; i left = nodes[2*i + 1];nodes[i]->right = nodes[2*i + 2];}}if (isequal(nodes[0], nodes[0])) {cout >target;int sum=binarysearch(nums,target);couta[i].x;cin>>a[i].y;}sort(a,a+n,cmp);for(int i=1;i>b>>w;n=max({n,a,b});//找出最大有几个点；f[a][b]=min(f[a][b],(long long)w);//给各个边赋值，其余没赋值的均为max; }n++;bool nic=true;for(int k=0;k>a[i][1]>>a[i][2];} sort(a.begin(),a.end(),cmp);vectorp(n+1,0);vectorans(n+1,0);for(int i=1;i0;j--){if(a[j][1]a[i];}for(int i=1;i>sink;vector graph(v,vector(v));for (int i = 0; i > graph[i][j]; } } int result=maxFlow(graph,source,sink); coutu>>v;graph[u-1].push_back(v-1);graph[v-1].push_back(u-1);}bool re=iserfentu(graph,n);cout