wordpress能开发商城网站,响应式网站搭建百度小程序,重庆招聘网,福州专业网站设计题目大意#xff1a;
有n个出车安排#xff0c;一辆车能接到这个安排的条件是#xff1a;1、这辆车第一次发车#xff1b;2、这辆车接了上一个安排#xff0c;回到这个安排的起点的时间正好是这个安排的前一分钟或者更早
解题报告#xff1a; 建图然后跑最小路径覆盖。…题目大意
有n个出车安排一辆车能接到这个安排的条件是1、这辆车第一次发车2、这辆车接了上一个安排回到这个安排的起点的时间正好是这个安排的前一分钟或者更早
解题报告 建图然后跑最小路径覆盖。就是答案。注意搭边的条件不是光看距离还要加上每个任务的起点到终点的时间。
AC代码116ms
#includebits/stdc.husing namespace std;
int n;
int a,b;
int line[1005][1005];
int nxt[1005];
bool used[1005];
struct Node {int x[3],y[3];int time;int dis;
} node[10005];
bool find(int x) {for(int i 1; in; i) {if(line[x][i] 1 used[i] 0) {used[i]1;if(nxt[i] 0 || find(nxt[i])) {nxt[i]x;return 1;}}}return 0;
}
int main()
{int t;cint;while(t--) {scanf(%d,n);memset(line,0,sizeof line);memset(nxt,0,sizeof nxt);for(int i 1; in; i) {scanf(%d:%d %d %d %d %d,a,b,node[i].x[0],node[i].y[0],node[i].x[1],node[i].y[1]);node[i].time a*60b;node[i].dis abs(node[i].x[0]-node[i].x[1]) abs(node[i].y[0] - node[i].y[1]);}for(int i 1; in; i) {for(int j 1; jn; j) {//或者ji1都可以acif(node[i].dis node[i].time abs(node[j].x[0]-node[i].x[1]) abs(node[j].y[0] - node[i].y[1]) node[j].time) {line[i][j] 1;}}}int ans 0;for(int i 1; in; i) {memset(used,0,sizeof used);if(find(i)) ans;}printf(%d\n,n-ans);}return 0 ;
}
AC代码226ms
//邻接表会快多少
#include cstdio
#include cstring
#include algorithm
#include cstdlib
#include vector
using namespace std;const int N 505;int t, n;struct People {int s, x1, y1, x2, y2;void read() {int h, m;scanf(%d:%d%d%d%d%d, h, m, x1, y1, x2, y2);s h * 60 m;}bool operator (const People c) const {return s c.s;}
} p[N];vectorint g[N];bool judge(People a, People b) {int tmp a.s abs(a.x2 - a.x1) abs(a.y2 - a.y1) abs(a.x2 - b.x1) abs(a.y2 - b.y1);if (tmp b.s) return true;return false;
}int match[N], vis[N];bool dfs(int u) {for (int i 0; i g[u].size(); i) {int v g[u][i];if (vis[v]) continue;vis[v] 1;if (match[v] -1 || dfs(match[v])) {match[v] u;return true;}}return false;
}int hungary() {int ans 0;memset(match, -1, sizeof(match));for (int i 0; i n; i) {memset(vis, 0, sizeof(vis));if (dfs(i)) ans;}return ans;
}int main() {scanf(%d, t);while (t--) {scanf(%d, n);for (int i 0; i n; i) {g[i].clear();p[i].read();}sort(p, p n);for (int i 0; i n; i)for (int j i 1; j n; j) {if (judge(p[i], p[j]))g[i].push_back(j);}printf(%d\n, n - hungary());}return 0;
}
总结
想想为什么 j1或者ji1都可以AC
20190504因为你sort了这样j1~i这一部分都没必要遍历了因为肯定不符合题意。
