首页 > 试题广场 >

项目经理

[编程题]项目经理
  • 热度指数:1736 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
A公司和B公司有n个合作的子项目,每个子项目由A公司和B公司各一名员工参与。一名员工可以参与多个子项目。

一个员工如果担任了该项目的项目经理,它需要对所参与的该项目负责。一个员工也可以负责多个项目。

A公司和B公司需要保证所有子项目都能有人负责,问最少需要指定几名项目经理?

输入描述:
第一行为A公司的的人员id列表, 0< id数量 < 10000,用空格切分
第二行为B公司的人员id列表, 0< id数量 < 10000,用空格切分
第三行为有已经有多少个匹配数子项目合作关系n
下面有n行,每一行为每个子项目的合作对应关系,为两个id,第一个为A公司的员工id,第二个为B公司的员工id,用空格区分


输出描述:
一个整数,A公司和B公司合起来至少需要指定几名项目经理
示例1

输入

0 1 2
3 4 5
6
0 4
0 3
1 3
1 4
2 5
2 4

输出

3

说明

可行的一个保留人员方案是留下0,1,2即可,这样即可保证所有的子项目都有人cover到。
这道题看起来应该是 二分图最小点覆盖
由Konig定理可知,最小点覆盖数=最大匹配边数
转换为二分图的最大匹配问题
(虽然这是一道板子题,但还是有点离谱
发表于 2021-01-16 20:03:13 回复(0)
是我没读懂题吗,不就指定1个人负责所有项目就完了吗,最少一人
发表于 2021-01-06 19:19:46 回复(3)
import java.util.Arrays;
import java.util.Scanner;

/**
 * 匈牙利算法
 * 求二分图的最大匹配
 */
public class Main {
    // 存放A员工匹配的B员工id
    static int[] match;
    // B员工是否已匹配
    static boolean[] used;
    // A、B员工共同参与的项目,连线为1,不连线为0
    static int[][] map;

    public static int solve(int[] companyA, int[] companyB) {
        Arrays.fill(match, -1);
        int res = 0;
        for (int i : companyA) {
            Arrays.fill(used, false);
            if (find(companyB, i)) {
                res++;
            }
        }
        return res;
    }

    public static boolean find(int[] companyB, int index) {
        for (int j : companyB) {
            if (map[index][j] == 1 && !used[j]) {
                used[j] = true;
                if (match[j] == -1 || find(companyB, match[j])) {
                    match[j] = index;
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String A = s.nextLine();
        String B = s.nextLine();
        String[] sa = A.split(" ");
        String[] sb = B.split(" ");
        int[] companyA = new int[sa.length];
        int[] companyB = new int[sb.length];
        int a = 0, b = 0;
        int maxa = 0, maxb = 0;
        for (String str : sa){
            int c = Integer.parseInt(str);
            companyA[a++] = c;
            maxa = Math.max(maxa, c);
        }
            
        for (String str : sb){
            int c = Integer.parseInt(str);
            companyB[b++] = c;
            maxb = Math.max(maxb, c);
        }
        match = new int[maxb+1];
        used = new boolean[maxb+1];
        map  = new int[maxa+1][maxb+1];
        
        int n = s.nextInt();
        while (n-- > 0) {
            int fir = s.nextInt();
            int sec = s.nextInt();
            map[fir][sec] = 1;
        }
        System.out.println(solve(companyA, companyB));
        s.close();
    }
}

发表于 2022-03-16 10:34:16 回复(0)


import java.util.*;



public class Main
{


public static void main(String[] args)
{
Scanner sc = new Scanner(System.in);
String left = sc.nextLine();
String right = sc.nextLine();
int n = sc.nextInt();
String[] l = left.split(" ");
String[] r = right.split(" ");
int[] a = new int[l.length];
int[] b = new int[r.length];
HashMap<Integer, Integer> num = new HashMap<Integer, Integer>();
int count = 0;
int length = a.length + b.length;
int[][] map = new int[length][length];
int[] match = new int[length];
Boolean[] used = new Boolean[length];
for (int i = 0; i < length; i++)
{
Arrays.fill(used, false);
Arrays.fill(map[i], -1);
Arrays.fill(match, -1);
}

for (int i = 0; i < a.length; i++)
{
a[i] = Integer.valueOf(l[i]);
num.put(a[i], i);
}
for (int i = 0; i < b.length; i++)
{
b[i] = Integer.valueOf(r[i]);
num.put(b[i], i + a.length);
}
for (int i = 0; i < n; i++)
{
int xx = sc.nextInt();
int yy = sc.nextInt();
map[num.get(xx)][num.get(yy)] = 1;
map[num.get(yy)][num.get(xx)] = 1;
}
search(num, a, b, map, match, used, length);
for (int i = 0; i < length; i++)
{
if(match[i] != -1)
{
count++;
}
}
System.out.println(count/2);
}
public static Boolean findPath(HashMap<Integer, Integer> num, int[][] map, int x, Boolean[] used, int[] match, int length)
{
for (int i = 0; i < length; i++)
{
if(map[x][i] == 1)
{
if(used[i] == false)
{
used[i] = true;
if(match[i] == -1 || findPath(num, map, match[i], used, match, length))
{
match[x] = i;
match[i] = x;
return true;
}
}
}

}
return false;
}
public static void setUsed(Boolean[] used)
{
for (int i = 0; i < used.length; i++)
{
used[i] = false;
}
}
public static void search(HashMap<Integer, Integer> num, int[] a, int[] b, int[][] map, int[] match, Boolean[] used, int length)
{
for (int i = 0; i < a.length; i++)
{
if(match[num.get(a[i])] == -1)
{
setUsed(used);
findPath(num, map, num.get(a[i]), used, match, length);
}
}
for (int i = 0; i < b.length; i++)
{
if(match[num.get(b[i])] == -1)
{
setUsed(used);
findPath(num, map, num.get(b[i]), used, match, length);
}
}
}





}
编辑于 2021-04-29 00:39:25 回复(0)
思路是:基于二分图最小点覆盖进行求解,由koing定理二分图中的最小点覆盖数=最大匹配数。
想吐槽的是:这个试题输出的 用例数据都不分行,完全没办法用于本地调试,简直是XXXXXX。
Python代码如下:
if __name__ == '__main__':
    def dfs(x, graph_dict, visited, left):
        b_members = graph_dict[x]
        for b_m in b_members:  # 同一次 增广路寻找中,若v曾经被达到过,则跳过。
            if visited[b_m] == 0:  # 若x能到达的 右部结点 b_m 为非匹配点,则找到了一条长度为1的增广路,记:left[b_m] = x
                visited[b_m] = 1
                if b_m not in left.keys():
                    left[b_m] = x
                    return True
                else:
                    # 若 b_m 为匹配点,则递归的从left[b_m]出发寻找增广路,回溯时记:left[b_m] = x
                    dfs(left[b_m], graph_dict, visited, left)
                    left[b_m] = x
                    return True
        return False


    # a_company = list(map(int, input().split(' ')))
    # b_company = list(map(int, input().split(' ')))
    # n = int(input())
    # projects = []
    # for _ in range(n):
    #     temp = list(map(int, input().split(' ')))
    #     projects.append(temp)
    a_company = [0, 1, 2]
    b_company = [3, 4, 5]
    projects = [[0, 4], [0, 3], [1, 3], [1, 4], [2, 5], [2, 4]]
    graph_dict = {}
    for p in projects:
        if p[0] not in graph_dict.keys():
            graph_dict[p[0]] = []
        graph_dict[p[0]].append(p[1])
    # 根据建立的二分图,寻找 最大匹配数 = 最小点覆盖数
    visited = {}  # 记录右部节点是否被匹配过
    for b_m in b_company:
        visited[b_m] = 0
    left = {}  # 匹配右部i点的左部节点
    ans = 0
    for a_m in a_company:  # 从a公司的任一节点出发,依次寻找增广路,并查找返回结果
        if dfs(a_m, graph_dict, visited, left):
            ans += 1
    print(ans)


发表于 2021-04-03 21:08:56 回复(0)
import collections

a = list(map(int, input().split()))
b = list(map(int, input().split()))
n = int(input())


tmp1 = collections.defaultdict(list)
tmp2 = collections.defaultdict(list)
tmp3 = collections.defaultdict(set)
for i in range(n):
    x, y = list(map(int, input().split()))

    tmp3[x].add(y)
m = 20000
st = [False] * m
match = [-1] * m


def find(x, tmp):
    #print(x,match)
    for i in tmp[x]:
        #print(i)

        if st[i] == False:
            st[i] = True
            if (match[i] == -1 or find(match[i], tmp)):
                match[i] = x
                return True
    return False


res = 0

for i in a:
    if (find(i, tmp3)):
        st = [False] * m
        res += 1;
#print(match,a)
print(res)

二分图:一个二分图中的最大匹配数等于这个图中的最小点覆盖数
注意:

  1. x-->y 可能有重复,最好用set筛一下
  2. 莫名其妙数组越界,直接开到最大
  3. 实际上是dfs
发表于 2021-02-18 22:46:14 回复(0)
/**
   匈牙利算法
*/
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
public class Main {

    static int n, idx, N = 20010, M = 2 * N;
    static int[] h = new int[N], e = new int[M], ne = new int[M];
    static int[] v1 = new int[N], v2 = new int[N];
    static int[] match = new int[N];
    static boolean[] st = new boolean[N];
    static int res = 0;
    static void add(int a, int b){
        e[idx] = b;
        ne[idx] = h[a];
        h[a] = idx ++;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] arr = bf.readLine().split(" ");
        String[] brr = bf.readLine().split(" ");
        for(int i = 1; i <= arr.length; i ++ ){
            v1[i] = Integer.parseInt(arr[i - 1]);
        }
        for(int i = 1; i <= brr.length; i ++){
            v2[i] = Integer.parseInt(brr[i - 1]);
        }

        n = Integer.parseInt(bf.readLine());
        Arrays.fill(h, -1);
        for(int i = 1; i <= n; i ++){
            String[] crr = bf.readLine().split(" ");
            int a = Integer.parseInt(crr[0]), b = Integer.parseInt(crr[1]);
            add(a, b); add(b, a);
        }

        for(int i = 1; i <= arr.length; i ++){
            int u = v1[i];
            Arrays.fill(st, false);
            if(find(u))
                res ++;
        }

        System.out.println(res);

    }

    static boolean find(int u){

        for(int i = h[u]; i != -1; i = ne[i]){
            int j = e[i];
            if(st[j]) continue;
            st[j] = true;
            if(match[j] == 0 || find(match[j])){
                match[j] = u;
                return true;
            }
        }
        return  false;
    }
}

发表于 2021-08-20 14:29:09 回复(0)
终究是一个人扛起了所有。(对吗?😂)
编辑于 2021-01-13 21:16:28 回复(0)
考察这种算法吗?惊了
发表于 2022-03-30 14:50:25 回复(0)
看底下的答案的方式就是Y总那边过来的。 可能是提高课的模板题?
是TMD真的离谱啊, 匈牙利算法也要考,我吐了。
用map构建邻接表,然后套板子。
import java.util.*;

public class Main {
    
    // 邻接矩阵
    public static Map<Integer, List<Integer>> map = new HashMap<>();
    public static boolean[] vis = new boolean[10010];
    public static int[] match = new int[10010];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 初始化第一个数组
        String[] tmp = sc.nextLine().split(" ");
        int n = tmp.length;
        int[] v1 = new int[n];
        for (int i = 0; i < n; i++) {
            v1[i] = Integer.parseInt(tmp[i]);
            map.put(v1[i], new ArrayList<>());
        }
        
        // 初始化第二个数组
        String[] tmp1 = sc.nextLine().split(" ");
        int m = tmp1.length;
        int[] v2 = new int[m];
        for (int i = 0; i < m; i++) {
            v2[i] = Integer.parseInt(tmp1[i]);
        }
        
        // 构建领接矩阵
        int k = sc.nextInt();
        while (k-- > 0) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            map.get(x).add(y);
        }
        
        // 匈牙利算法
        int res = 0;
        for (int i = 0; i < n; i++) {
            int num = v1[i];
            Arrays.fill(vis, false);
            if (find(num)) res++;
        }
        System.out.println(res);
        
    }
    // 匈牙利算法
    public static boolean find(int x) {
        // 得到边
        List<Integer> list = map.get(x);
        for (int i = 0; i < list.size(); i++) {
            int y = list.get(i);
            // 没有访问过
            if (vis[y]) continue;
            vis[y] = true;
            // 名花无主 或者能腾一个位置出来
            if (match[y] == 0 || find(match[y])) {
                match[y] = x;
                return true;
            }
        }
        return false;
    }
}


发表于 2022-03-05 20:35:03 回复(0)
加一个源点和一个汇点,转化为最大流问题。
发表于 2021-08-21 13:34:12 回复(0)
#include<bits/stdc++.h>

using namespace std;

vector<int> get(string s, int diff) {
    vector<int> a;
    stringstream str(s);
    int temp;
    while (str >> temp) a.push_back(temp + diff);
    return a;
}

const int maxn = 20100;
vector<vector<int>> e;
int match[maxn];
bool vis[maxn];
int ans;

bool dfs(int u) {
    for (int v:e[u]) {
        if (!vis[v]) {
            vis[v] = true;
            if (match[v] == -1 || dfs(match[v])) {
                match[v] = u;
                match[u] = v;
                return true;
            }
        }
    }
    return false;
}

int main() {
    vector<int> a, b;
    string s;
    getline(cin, s);
    a = get(s, 0);
    getline(cin, s);
    b = get(s, 0);
    int n;
    cin >> n;
    e = vector<vector<int>>(maxn);
    for (int i = 0; i < n; i++) {
        int u, v;
        cin >> u >> v;
       // v+=10000;
        e[u].push_back(v);
        e[v].push_back(u);

    }
    ans = 0;
    memset(vis, 0, sizeof(vis));
    memset(match, -1, sizeof(match));
    for (int i = 0; i < a.size(); i++) {
        if (match[a[i]] == -1) {
            memset(vis, 0, sizeof(vis));
            if (dfs(a[i])) ans++;
        }
    }
    cout << ans << endl;
}

发表于 2021-03-26 17:37:19 回复(0)
白嫖答案失败。。。。
发表于 2021-02-17 12:11:25 回复(0)
按照每一个项目至少有一个经理dfs, 第一个case就超时了,卒
def readToInt():
    return [int(n) for n in input().split()]

companyA = readToInt()
companyB = readToInt()
pairs = []
for _ in range(int(input())):
    pairs.append(readToInt())

count = float("inf")

def dfs(index, selected):
    global count
    if index >= len(pairs):
        count = min(count, len(selected))
        return
    if len(selected) >= count:
        return
    pair = pairs[index]
    if pair[0] in selected&nbs***bsp;pair[1] in selected:
        dfs(index + 1, selected)
    else:
        selected.add(pair[0])
        dfs(index + 1, selected)
        selected.remove(pair[0])
        selected.add(pair[1])
        dfs(index + 1, selected)
        selected.remove(pair[1])

dfs(0, set())
print(count)


发表于 2021-01-21 11:41:29 回复(1)