Machine Schedule

The input file for this program consists of several configurations.

The first line of one configuration contains three positive integers: $n, m (n, m \lt 100)$ and $k (k \lt 1000)$ .

The following k lines give the constrains of the k jobs, each line is a triple: i, x, y.

The input will be terminated by a line containing a single zero.

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 376K, 提交时间: 2020-08-14 14:55:49

#include<bits/stdc++.h>
using namespace std;
const int N = 110;
int n, m, k, f[N], ans;
bool v[N];
vector<int>e[N];

bool dfs(int x) {
	for (int i = 0; i < e[x].size(); ++i) {
		int y = e[x][i];
		if (v[y])continue;
		v[y] = true;
		if (!f[y] || dfs(f[y])) {
			f[y] = x;
			return 1;
		}
	}
	return 0;
}

int main() {
	//freopen("in.txt", "r", stdin);
	while (cin >> n && n) {
		cin >> m >> k;
		for (int i = 0; i < n; ++i)e[i].clear();
		for (int i = 0; i < k; ++i) {
			int x, y;
			cin >> i >> x >> y;
			if (x && y)e[x].push_back(y);
		}
		memset(f, 0, sizeof f);
		ans = 0;
		for (int i = 1; i < n; ++i) {
			memset(v, 0, sizeof v);
			ans += dfs(i);
		}
		cout << ans << endl;
	}
}

C++ 解法, 执行用时: 5ms, 内存消耗: 436K, 提交时间: 2022-04-15 21:23:59

#include<bits/stdc++.h>
using namespace std;
int n,m,k,mapn[101][101],linker[101],used[101],op,x,y;
bool dfs(int u){
    for(int v=0;v<m;v++)if(mapn[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){linker[v]=u;return 1;}}
    return 0;
}
int main(){
    while(cin>>n&&n){
        memset(mapn,0,sizeof mapn);
        cin>>m>>k;
        for(int i=0;i<k;i++){cin>>op>>x>>y;if(x>0&&y>0)mapn[x][y]=1;}
        int res=0;
        memset(linker,-1,sizeof linker);
        for(int u=0;u<n;u++){memset(used,0,sizeof used);if(dfs(u))res++;}
        cout<<res<<"\n";
    }
    return 0;
}

详情