学步园

题意：给出n个岛的坐标，要从第一个到跳到第二个岛，跳的时候有个距离限制，求出这个距离的最小值。 思路：刚开始限制距离为两岛的直接距离，用二分每得到一个距离mid，判断1个2是否能连通。就求出最小的限制距离了。 #include<string.h> #include<math.h> #include<stdio.h> const int N=210; int f[N],n; double map[N][N]; struct node { int x,y; }p[N]; double dist(int i,int j) { return sqrt...

先选一点为根节点找出所有父节点i到下面所有点距离和dp[i]，该父节点下面有多少个点Node[i]。 然后求出所有节点的所有非子节点到该点的距离dp1[v]+=(dp1[u]+(dp[u]-dp[v]-Node[v]-1)+n-Node[v]-1) dp[u]-dp[v]-Node[v]-1:u的子节点中除了v这一部分子节点到u的距离 n-Node[v]-1：非v的字节点的个数 #include<stdio.h> #include<string.h> #define N 50002 #define inf 0x3fffffff int head[N],num,vis[N],dp...

题意：有n个地方，m个任务，每个任务给出地点，开始的时间和完成需要的时间，问最少派多少工人去可以完成所有的任务。给出任意两点直接到达需要的时间，-1代表不能到达。 思路：很明显的最小路径覆盖问题，刚开始脑子抽了，没求最短路直接就做了，题目只给了两点间直接到达的时间，还可以间接到达，用floyd求出最短路。。。 #include<stdio.h> #include<string.h> const int N=300; const int inf=0x3ffffff...

刚学最大流算法，一道简单的最大流问题，思路就是找出每条从s->t的路径中最小的残量a[t]（最大流量-已流的流量）将路径上的流量都增加a[t]，直到残量为0； #include<iostream> #include<stdio.h> #include<queue> #include<string.h> #define INF 99999999 using namespace std; int m,n,map[250][250],a[250],flow[250][250],p[250]; int EK(int s,int t) { int sum=0; queue<int&g...

非常好的一道拆点题目，终于学会isap了，递归的，这几天要把非递归实现的敲出来，， 题意：给出蜥蜴可以跳的最大距离,从一根柱子跳向可以到达的任意柱子，每个柱子有高度，蜥蜴没跳一次柱子会下降1米，问有多少蜥蜴跳不出所给的图。 建图：源点与每个蜥蜴所在的柱子建边流量为1，应为柱子间可以互相达到的，所以每个柱子应该拆成两个点，每根柱子相当于一条边，流量为柱子的高度，没两个可以互相到达的柱子间建边（一根柱子的...

题意：每个买猪的人手上都有一些钥匙，可以打开相应的猪圈，每个人只能在自己打开的猪圈买猪，每个人买完时Mirko可以把打开的猪圈的猪任意分配（只能在打开的猪圈之间），然后锁上猪圈。问最多能卖出多少猪。 建图：如果来的人打开的猪圈之前都没打开过，就最多能买打开猪圈的猪数量了，，如果有猪圈已经被打开了，那么他可以获得上次打开这个猪圈的人当时打开的所有猪圈猪的数量除去他已经买走的数量的购买权。每个顾客为一个...

题意：每头牛有想吃的食物和饮料，每头牛最多只能吃一种食物和一种饮料，给出牛的个数，食物和饮料的种类数，每头牛想要的食物和饮料的种类。 刚开始想着把牛放中间，从汇点到食物，食物到牛，牛到饮料，饮料到汇点建图，当时没想清楚就敲了，结果wrong了，后来一想这样建图的话，经过没头牛的流量就不是1了，果断拆点，把每头牛拆成两个点，流量为1 #include<stdio.h> #include<string.h> #define N 500 #...

题意：有k台挤奶机，c头奶牛，给出这k+c个实体间的距离，求出每头奶牛都到一台挤奶机去，怎么分配使奶牛走的最大距离最小。 用二分枚举最大距离，，，， #include<stdio.h> #include<string.h> #define N 500 #define inf 0x3fffffff int map[N][N],dis[N],gap[N],head[N],num,n,m,D,start,end,ans; struct edge { int st,ed,flow,next; }E[N*40]; void addedge(int x,int y,int w) { E[num].st=x;E[num].e...

题意：把n个好友分到m个组。求每个组的最大人数最小可以是多少人，，， 最大流+二分，，，，isap跑得还是挺快的，，， #include<stdio.h> #include<string.h> const int N=1510; const int inf=0x3fffffff; int dis[N],gap[N],head[N],num,start,ans,end,first[N],nume,n,m; struct edge { int st,ed,flow,next; }E[510000]; struct node { int x,next; }e[510000]; void addedge(int x,int y,int w) { ...

题意：有n块草地，一些奶牛在草地上吃草，草地间有m条路，一些草地上有避雨点，每个避雨点能容纳的奶牛是有限的，给出通过每条路的时间，问最少需要多少时间能让所有奶牛进入一个避雨点。 两个避雨点间可以相互到达，所以必须要拆点，如果i-->j可以到达,加边i->j+n，流量无穷大，当然i->i+n也必须有边，，， Folyd要用long long，，，，， #include<stdio.h> #include<string.h> const int N=410;...