混合图的欧拉回路问题
题目地址
欧拉回路问题
1 定义
欧拉通路 (Euler tour)——通过图中每条边一次且仅一次，并且过每一顶点的通路。
欧拉回路 (Euler circuit)——通过图中每条边一次且仅一次，并且过每一顶点的回路。
欧拉图——存在欧拉回路的图。
2 无向图是否具有欧拉通路或回路的判定
G有欧拉通路的充分必要条件为：G 连通，G中只有两个奇度顶点(它们分别是欧拉通路的两个端点)。
G有欧拉回路(G为欧拉图)：G连通，G...
阅读全文
点击打开链接
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
const int N = 100005;
const int M = 10;
const int mod = 100003;
int head[N], num, a[M], snow[N][M];
struct node
{
int pos, next;
}e[N];
void hash(int val, int pos)
{
e[num].pos = pos;
e[num].next = head[val];
head[val] = num++;
}
int check(int a, int b)
{
int i, j;
for(i=0; i...
阅读全文
HDU
2222 Keywords Search
题意：给定N(N <= 10000)个长度不大于50的模式串，再给定一个长度为L(L
<= 106)目标串，求目标串出现了多少个模式串。
题解：AC自动机模板题，在Trie的每个结点设一个Count表示统计以这个结点结尾的模式串的个数（因为模式串可能有相同的），Insert的时候统计，Find的时候找到一个是模式串结尾结点的时候统计Count,并把这个结点的Count置0，表示已经统计过了。累加的Count即为答案。
#in...
阅读全文
题意：给出两个字符串，求最长公共子串的长度。
题解：首先将两个字符串连在一起，并在中间加一个特殊字符（字串中不存在的）分割，然后两个串的最长公共字串就变成了所有后缀的最长公共前缀。这时就要用到height数组，因为任意两个后缀的公共前缀必定是某些height值中的最小值，而这个值如果最大则一定是height中的最大值。在此题中还要注意height最大一定要在两个值所代表的后缀分属不同的字符串地前提下。
#include<...
阅读全文
点击打开链接
求MST的最长边~
prim
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#define Min(a,b) (a)<(b)?(a):(b)
using namespace std;
const int INF = 1000000000;
const int maxn = 2000 + 5;
struct pto
{
int v, len;
};
vector<pto> G[maxn];
bool vis[maxn];
int dis[maxn];
int n, m;
int Prim()
{
int i, j, p, ans, minc;
...
阅读全文
次小生成树
求最小生成树时，用数组Max[i][j]来表示MST中i到j的最大边权。
求完后，直接枚举所有不在MST中的边，替换掉最大边权的边，更新答案。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 110;
const int INF = 1e9;
bool vis[maxn];
int d[maxn];
int pre[maxn];
int Max[maxn][maxn];
bool used[maxn][maxn];
int g[maxn][maxn];
int n, m;
...
阅读全文
点击打开链接
两次求最短路（第二次把边反向求）
1、spfa
//poj 3268 Silver Cow Party
//SPFA
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int M = 100000 + 100;
const int N = 1000 + 100;
const int inf = 1<<25;
struct Graph {
int head[N], next[M], to[M], val[M], cnt, n;
void init(int num)
{
memset(head, -1, sizeo...
阅读全文
题目大意：
有一个序列，题目用n个整数组合 [ai,bi,ci]来描述它，[ai，bi，ci]表示在该序列中处于[ai，bi]这个区间的整数至少有ci个。如果存在这样的序列，请求出满足题目要求的最短的序列长度是多少。如果不存在则输出 -1。
输入：第一行包括一个整数n，表示区间个数，以下n行每行描述这些区间，第i+1行三个整数ai，bi，ci，由空格隔开，其中0<=ai<=bi<=50000 而且 1<=ci<=bi-ai+1。
输出：一行，输出满足要求...
阅读全文
点击打开链接
SPFA + A*
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
int v, dis, f, next;
friend bool operator <(node a, node b){
return a.f>b.f;
}
};
const int INF = 1e9;
const int maxn = 1005;
const int maxm = 100005;
node edge[maxm], edgef[maxm];
int head[maxn], e, headf[maxn], dis[maxn...
阅读全文
题目链接: 点击打开链接
题意：
给定一个有向图，求：
1) 至少要选几个顶点，才能做到从这些顶点出发，可以到达全部顶点
2) 至少要加多少条边，才能使得从任何一个顶点出发，都能到达全部顶点
顶点数<= 100
求完强连通分量后，缩点，计算每个点的入度，出度。
第一问的答案就是入度为零的点的个数，
第二问就是max(n,m) // 入度为零的个数为n, 出度为零的个数为m. //kuangbin巨巨分析很棒！
#include<cstdio&...
阅读全文