C++14(g++5.4) 解法, 执行用时: 214ms, 内存消耗: 7264K, 提交时间: 2019-03-14 17:58:20

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 505;
const int MAXP = 1005;
const int INF = 1e9 + 10;
template <typename T> void chkmax(T &x, T y) {x = max(x, y); }
template <typename T> void chkmin(T &x, T y) {x = min(x, y); } 
template <typename T> void read(T &x) {
	x = 0; int f = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') f = -f;
	for (; isdigit(c); c = getchar()) x = x * 10 + c - '0';
	x *= f;
}
template <typename T> void write(T x) {
	if (x < 0) x = -x, putchar('-');
	if (x > 9) write(x / 10);
	putchar(x % 10 + '0');
}
template <typename T> void writeln(T x) {
	write(x);
	puts("");
}
struct edge {int dest, flow; unsigned home; };
int n, m, v[MAXN];
int s, t, flow, dist[MAXP];
int x[MAXN], y[MAXN], d[MAXN];
int len[MAXN][MAXN], bak[MAXN][MAXN];
unsigned curr[MAXP];
vector <edge> a[MAXP];
int dinic(int pos, int limit) {
	if (pos == t) return limit;
	int used = 0, tmp;
	for (unsigned &i = curr[pos]; i < a[pos].size(); i++) {
		if (a[pos][i].flow && dist[pos] + 1 == dist[a[pos][i].dest] && (tmp = dinic(a[pos][i].dest, min(limit - used, a[pos][i].flow)))) {
			used += tmp;
			a[pos][i].flow -= tmp;
			a[a[pos][i].dest][a[pos][i].home].flow += tmp;
		}
		if (used == limit) return used;
	}
	return used;
}
bool bfs() {
	static int q[MAXP];
	static int l = 0, r = -1;
	for (int i = 0; i <= r; i++)
		dist[q[i]] = 0;
	l = 0, r = -1;
	q[++r] = s; dist[s] = 1;
	while (l <= r) {
		int tmp = q[l++];
		for (unsigned i = 0; i < a[tmp].size(); i++)
			if (a[tmp][i].flow && dist[a[tmp][i].dest] == 0) {
				dist[a[tmp][i].dest] = dist[tmp] + 1;
				q[++r] = a[tmp][i].dest;
			}
	}
	return dist[t] != 0;
}
void addedge(int s, int t, int flow) {
	a[s].push_back((edge) {t, flow, a[t].size()});
	a[t].push_back((edge) {s, 0, a[s].size() - 1});
}
int main() {
	read(n), read(m);
	for (int i = 1; i <= n; i++)
		read(v[i]);
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++) {
		read(len[i][j]);
		if (i != j) len[i][j] += v[j];
		bak[i][j] = len[i][j];
	}
	for (int i = 1; i <= n; i++)
	for (int j = 1; j <= n; j++)
	for (int k = 1; k <= n; k++)
		chkmin(len[j][k], len[j][i] + len[i][k]);
	s = 0, t = m * 2 + 1;
	for (int i = 1; i <= m; i++) {
		read(x[i]), read(y[i]), read(d[i]);
		addedge(s, i, 1);
		addedge(i + m, t, 1);
	}
	for (int i = 1; i <= m; i++)
	for (int j = 1; j <= m; j++)
		if (d[j] - d[i] >= bak[x[i]][y[i]] + len[y[i]][x[j]]) addedge(i, j + m, 1);
	while (bfs()) {
		memset(curr, 0, sizeof(curr));
		flow += dinic(s, INF);
	}
	printf("%d\n", m - flow);
	return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 161ms, 内存消耗: 3056K, 提交时间: 2022-10-04 22:35:37

#include<bits/stdc++.h>
using namespace std;
#define N 505
struct flight {
	int u,v,t;
}q[N];
vector<int>g[N];
int n,m,ans;
int f[N][N],p[N],d[N][N],match[N];
bool vis[N];
void floyd() {
    for(int k=1;k<=n;k++) 
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=n;j++)
    			f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
}
int hungary(int u) {
	for(auto v:g[u]) {
		if(!vis[v]) {
			vis[v]=1;
			if(!match[v]||hungary(match[v])) {
				match[v]=u;
				return 1;
			}
		}
	}
	return 0;
}
int main() {
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d",p+i);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++) {
			scanf("%d",&d[i][j]);
			f[i][j]=d[i][j]+(i==j?0:p[j]);
		}
	floyd();
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].t);	
	for(int i=1;i<=m;i++)
		for(int j=1;j<=m;j++) {
            int t = q[j].t - q[i].t - d[q[i].u][q[i].v] - p[q[i].v];
			if (t >= f[q[i].v][q[j].u])  g[i].push_back (j);
        }
	for(int i=1;i<=m;i++) {
    	memset(vis,0,sizeof(vis));
    	ans+=hungary(i);
    }
	cout<<m-ans;
}