题意：从1到n，要走不少于K条路，每条路不能重复走，点可以重复走，求所走的路中最长的最小，，
找出距离的最大值，然后二分，建图时符合的每条边链接的两点间建双向边，流量都为1，求最大流
#include<stdio.h>
#include<string.h>
const int N=210;
const int inf=0x3fffffff;
int dis[N],gap[N],head[N],num,start,end,ans,n,m;
struct edge
{
int st,ed,flow,next;
}E[200000];
struct node
{
int x,y,w...
阅读全文
题意：在一个会议室里有n种插座，每种插座一个,每个插座只能插一种以及一个电器（或者适配器）,有m个电器，每个电器有一个插头需要插在相应一种插座上,不是所有电器都能在会议室找到相应插座,有k种适配器，每种适配器可以有无限多数量,每种适配器(a, b)可以把b类插座变为a类插座,问最后有多少个电器无法使用。
建图：源点，电器，插座，汇点，，源点跟电器建边，流量为1，电器与对应的插座连边，流量为1，转换器(a,b),a与b连边...
阅读全文
最大流简单题，，这题重要的是知道了scanf("%s",str);sscanf(str,"(%d,%d)%d",&x,&y,&w);读入方式
#include<stdio.h>
#include<string.h>
const int N=210;
const int inf=0x3fffffff;
int dis[N],gap[N],head[N],num,start,end,ans,n,m;
struct edge
{
int st,ed,flow,next;
}E[21000];
struct node
{
int x,y,w;
}P[40000];
void addedge(int x,int y,int w)
{
E[num].st=x;E[num].ed=y;E[...
阅读全文
题意：起点开始有超过100个人，总共不会超过100个外星人，问把所有的外星人都搜出来花的最小时间。一条路径上的时间跟人数是无关的，只跟路径长度有关。
思路：刚开始人都在起点，当派一定人数去最近的外星人后，起点就变成两个了，然后从两个起点去最近的外星人，起点就变成三个了，，，，这就是最小生成树了。
#include<stdio.h>
#include<math.h>
#include<queue>
#include<stdlib.h>
#includ...
阅读全文
题意：给出一些城市的坐标，每个信号基站可以覆盖两个相邻的点，问最少要建多少个基站。
思路：我们要尽可能多的建立能覆盖两个城市的基站（二分匹配最大匹配），剩下的城市每个城市建立一个基站。先求出最大匹 配数k。n-k*2+k=n-k;
#include<stdio.h>
#include<string.h>
const int N=500;
int head[N],num,match[N],link[N],map[50][50];
int dir[4][2]={0,1,0,-1,1,0,-1,0};
struct edge
{...
阅读全文
题意：给定一棵N(1<= N <=10000)个结点的带权树，定义dist(u,v)为u,v两点间的最短路径长度，路径的长度定义为路径上所有边的权和。再给定一个 K ，如果对于不同的两个结点a,b，如果满足dist(a,b) <=K，则称(a,b)为合法点对。求合法点对个数。
思路：看了论文《分治算法在树的路径问题中的应用》，里面讲解的很清楚，一条路径要么过根节点，要么在一颗子树中，所以用分治算法。找到树的重心作为根节点，这样每次树的...
阅读全文
题意：给一棵树，三种操作。将第i条边的权值改为v，将a到b的路径上的边的权值全部取反，求a到b路径上边的权值的最大值。
思路：明显的树链剖分，加上线段树的操作。因为有取反的操作所以每个区间要记录最大值和最小值。查询两点间的路径时，用求公共祖先的方式去求。
#include<iostream>
#include<stdio.h>
#include<string.h>
const int N=101000;
const int inf=0x3fffffff;
using namespace std;
in...
阅读全文
题意：给出两个数的最大公约数g，最小公倍数lcm，求出这两个数，有多种组合的，求出和最小的一组。
思路：g=gca(a,b);a*b=lcm*g;a/g*b/g=lcm/g;gcd(a/g,b/g)=1;就是把lcm/g分解成两个互质的因子。可以用Pollard rho分解子因子，然后再将相同的因子合并，再将因子分成两部分。
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include...
阅读全文
题意：给出p，a问p是不是以a为底的伪素数，如果p不是素数判断，是否a^p%p==a
#include<iostream>
#include<algorithm>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include<time.h>
#include<stdlib.h>
typedef __int64 LL;
LL a,b,sum;
const int S=20;//随机算法判定次数，S越大，判错概率越小
//***************Miller_Rab...
阅读全文
题意：更改四位数的门牌号(素数)，每次只能改一个数字，问最少多少次能改到目标数字。
思路：打表出四位的所有素数，然后建图，只有一个位数的数字不同的连边，跑最短路，，，
#include<iostream>
#include<stdio.h>
#include<queue>
#include<string.h>
const int N=10000;
const int inf=0x3fffffff;
using namespace std;
int link[N],prim[N],dis[N],vis[N];
struct edge
{
int st,ed,next...
阅读全文