最大流的入门题，第一次写了下ek算法，用了邻接矩阵。
EK算法的复杂度为O(n*m^2)
代码：
//EK算法求最大流问题二维数组实现
#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
#define INF 10000
#define maxn 205
using namespace std;
int n,m;
int path[maxn][maxn],pre[maxn],flow[maxn];
int vis[maxn];
int min(int x,int y)
{
return x<y?x:y;
}
int bfs()
{
...
阅读全文
一、四边形不等式基本理论
在动态规划的转移方程中，常见这样一种转移方程：
这两个定理证明在赵爽的《动态规划加速原理之四边形不等式》中给出了相关的证明。
二、四边形定理的应用
1、poj1160 题目大意：给定n个城市，在m个城市里建邮局，使所有城市到最近邮局的距离和最小。很容易得到这样的方程：
dp(i,j)=min(dp(i-1,k)+w(k+1,j)) , i-1<=k<j s(i-1,j)<=k<=s(i,j+1)
w(i,j)=w(i,j-1)+val[j]-val[(j+i)/...
阅读全文
A Dicey Problem
Time Limit: 1000MS
Memory Limit: 65536K
Total Submissions: 788
Accepted: 271
Description
The three-by-three array in Figure 1 is a maze. A standard six-sided die is needed to traverse the maze (the layout of a standard six-sided die is shown in Figure 2). Each maze has an initial position and an initial die configuration. In Figure 1, the starting
position is r...
阅读全文
最短路问题，要求出最短路的个数。
输出一条得到JavaBean最多的最短路径
#include<stdio.h>
#include<string.h>
#define inf 0x3fffffff
int n,m,map[510][510],dp[510],mark[510],dis[510],w[510],pre[510],link[510];
int st,ed;
void dijkstra()
{
int i,j,k,min;
memset(mark,0,sizeof(mark));//标记房间是否走过
memset(dp,0,sizeof(dp));//记录到达位置得到最多的JavaBean
memset(pre,-1,sizeof...
阅读全文
最短路问题，，求三点之间的最短路
给出n个电话连接在m个transfer stations上，给出transfer stations之间的距离，
给出三个电话，求把三个电话连通的最短距离
dijkstra可以求出一点到其余个点的最短距离，
枚举所有点到这三个点的最小距离之和，取最小值即可
#include<stdio.h>
#include<string.h>
#define inf 99999999
int n,m,map[510][510],vis[510],point[10010],dis[510][510],mark[510];
void dijks...
阅读全文
题意：n-1个ACM学生自愿者每天要从css(1站点)坐车到达剩下站点，每个人去一个站点，
到一天结束时要返回到css(1站点)，城市的交通系统是有向图，求n-1个学生车费最少。
分析：当学生去的时候相当于求点1到所有点的最短路。回来时，是求所有点到1的最短路，
数据很大肯定不能每个点求一次，建反图后就是求1到搜有点的最短路了，用dijkstra()可以解决,
数据太大，用dijkstra()+优先队列，总结果会超int，wrong了几次，，，，，，...
阅读全文
题意：John的农场里n块地，m条路连接两块地，k个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。
思路：虫洞连接的边是负权值的，如果途中存在一个负环的话，他可以沿着这个换一直走，时间肯定为负值。
#include<string.h>
#include<stdio.h>
const int N=510;
const int inf=0x3fffffff;
int start,num,n,dist[N...
阅读全文
思路：列出公式：设跳了a次后相遇，则
(x+am)%L=(y+bn)%L
(a(m-n))%L=(y-x)%L
就是解同余方程a*c≡d(L);
解线性同于方程：
ax≡b (mod n)的方程。此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。
在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。
对于线性同余方程
ax ≡ b (mod n) (1)
若 d = gcd(a, n)，d 整除 b ，那么b/d为整数。由裴蜀定理，存在整数对
(r,s) （可用辗转相除...
阅读全文
题意：给定一个64位整数，问是否为质数，如果不是，则输出其最小因子。
分析：经典题数学题，给的数太大，普通方法肯定超时，就在网上找了这个算法
miller_rabbin素数判定。若不是，则pollard_rho分解质因子，找到最小即可。
Miller-rabin算法是一个用来快速判断一个正整数是否为素数的算法。它利用了费马小定理，即：如果p是质数，且a，p互质，那么a^(p-1) mod p恒等于1。也就是对于所有小于p的正整数a来说都应该复合a^(p-1...
阅读全文
题意：给出n个字母的一些大小关系，判断能否拓扑排序或者出现了矛盾，如果是这两种情况要求出到第几组关系时就可以得到。否 则就是所给数据不完全。
思路：每读一组关系进行一次拓扑排序，如果排序成功或者出现矛盾记录第几组关系之后就不拓扑排序了，直接读完数据就行了。
#include<stdio.h>
#include<string.h>
#include<stack>
const int N=30;
using namespace std;
int map[N][N],insep...
阅读全文