关键词：
LINK：Lis-The Postman
看完题觉得 虽然容易发现是有向图欧拉回路 但是觉得很难解决这个问题。
先分析一下有向图的欧拉回路：充要条件 图中每个点的入度-出度=0且整张图是一个强连通分量。
证明：首先考虑前者 这个思想是 从一个点出去必然还能回来所以可以形成回路 后者保证了图是联通的。
但是注意观察题目中有一些比较好的条件 每两个点之间的边最多有两条且方向不同。
题目给了k条必须要要连续走的路径 容易想到多条路径可以合并在一起。
这个操作看起来难做 但是 把边进行标号 然后只需要前驱和后继进行合并即可。
判定条件：1 图中原本的点入度-出度=0.2 一条边在一条路径出现两次就是错的 3 一条边有多个前驱后继就是错的。
这样 我们可以把一些边给合并起来了。我们可以要求一走走完这些边。
4 这些边合并在一起后 存在环了那么肯定也走不了。
剩下的就是一个正常的图了 跑欧拉回路即可。
5 在新建的图中再次判断点的出度和入度。
6 最后需要判断图联通与否。
7 判断是否可以从1出发
8 虽然没要求输出方案但是这里点一下 倒序输出点 点和点相连就是边了 更快的方法 输出点的时候可以直接记录将这个点送进来的边是哪个直接输出边。
//#include<bitsstdc++.h>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdlib>
#include<queue>
#include<deque>
#include<stack>
#include<vector>
#include<algorithm>
#include<utility>
#include<bitset>
#include<set>
#include<map>
#define ll long long
#define db double
#define INF 1000000000000000ll
#define ldb long double
#define pb push_back
#define put_(x) printf("%d ",x);
#define get(x) x=read()
#define gt(x) scanf("%d",&x)
#define gi(x) scanf("%lf",&x)
#define put(x) printf("%d
",x)
#define putl(x) printf("%lld
",x)
#define gc(a) scanf("%s",a+1)
#define rep(p,n,i) for(RE int i=p;i<=n;++i)
#define go(x) for(int i=lin[x],tn=ver[i];i;tn=ver[i=nex[i]])
#define fep(n,p,i) for(RE int i=n;i>=p;--i)
#define pii pair<int,int>
#define mk make_pair
#define RE register
#define P 1000000007
#define S second
#define F first
#define gf(x) scanf("%lf",&x)
#define pf(x) ((x)*(x))
#define ull unsigned long long
#define ui unsigned
#define EPS 1e-8
#define mod 1000000007
#define sq sqrt
#define l(p) t[p].l
#define r(p) t[p].r
#define op(p) t[p].op
#define cnt(p) t[p].cnt
#define sum(p) t[p].sum
#define zz p<<1
#define yy p<<1|1
using namespace std;
char buf[1<<15],*fs,*ft;
inline char getc()
return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;
inline int read()
RE int x=0,f=1;RE char ch=getc();
while(ch<‘0‘||ch>‘9‘)if(ch==‘-‘)f=-1;ch=getc();
while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘;ch=getc();
return x*f;
const int MAXN=200010,maxn=50010;
int n,m,len,k,top;
int du[MAXN],w[MAXN],b[MAXN],s[MAXN];
map<int,int>H[maxn];
struct wyint x,y;t[MAXN];
int pre[MAXN],ne[MAXN],vis[MAXN];
int lin[MAXN],ver[MAXN],nex[MAXN],fir[MAXN];
inline void add(int x,int y,int w1)
ver[++len]=y;
nex[len]=lin[x];
lin[x]=len;
++du[x];--du[y];
fir[len]=w1;
//cout<<x<<‘ ‘<<y<<endl;
inline void js()puts("NIE");exit(0);
inline void dfs(int x,int fa)
for(int &i=lin[x];i;i=nex[i])
if(vis[i])continue;
vis[i]=1;
dfs(ver[i],i);
s[++top]=fa;
//put(x);
int main()
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
get(n);get(m);
rep(1,m,i)
int get(x),get(y);
t[i]=(wy)x,y;
++du[x];--du[y];
H[x][y]=i;
rep(1,n,i)if(du[i])js();
get(k);
rep(1,k,i)
int get(x);
int get(las);
rep(1,x-1,j)
int get(y);
if(H[las].find(y)==H[las].end())js();
b[j]=H[las][y];
if(w[b[j]]==i)js();
las=y;
rep(1,x-2,j)
if(!pre[b[j+1]])pre[b[j+1]]=b[j];
else if(pre[b[j+1]]!=b[j])js();
if(!ne[b[j]])ne[b[j]]=b[j+1];
else if(ne[b[j]]!=b[j+1])js();
int cnt=0;
rep(1,m,i)
if(!pre[i])
int j;++cnt;
for(j=i;ne[j];j=ne[j])++cnt;
add(t[i].x,t[j].y,i);
if(cnt<m||!lin[1])js();
rep(1,n,i)if(du[i])js();
dfs(1,0);--top;
rep(1,n,i)if(lin[i])js();
puts("TAK");
/*put(t[fir[s[top]]].x);
fep(top,1,i)
int j=fir[s[i]];
//put(t[j].x);
do
put(t[j].y);
j=ne[j];
while(j);
*/
return 0;
bzoj1520[poi2006]szk-schoolskm算法
【BZOJ1520】[POI2006]Szk-SchoolsDescriptionInputOutput如果有可行解,输出最小代价,否则输出NIE.SampleInput5112311513255415103331SampleOutput9题解：二分图最小权匹配裸题，可以直接无脑费用流，不过这里就当复习一下KM算法了。#include<cstdio>#inclu... 查看详情
bzoj1510[poi2006]kra-thedisks*
bzoj1510[POI2006]Kra-TheDisks题意：一个瓶子有n个节，每个节有一个宽度。现在要从上往下扔m个盘子，如果盘子的下一个位置宽度比该盘子的宽度小则盘子会停在这个位置。问最后一个盘子会停在那个位置。n，m≤300000。题解：首先利... 查看详情
[bzoj1510][poi2006]kra-thedisks_暴力
Kra-TheDisksbzoj-1510POI-2006题目大意：题目链接。注释：略。想法：不难发现其实只有前缀最小值是有效的。进而我们把盘子一个一个往里放，弄一个自底向上的指针往上蹦即可。时间复杂度$O(n)$。Code：#include<iostream>#include<cst... 查看详情
[bzoj1513][poi2006]tet-tetris3d
[BZOJ1513][POI2006]Tet-Tetris3D试题描述Task:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使... 查看详情
bzoj1513:[poi2006]tet-tetris3d
Description三维空间从上落下几个长方体,问最后的最高高度.Solution二维线段树.感觉这种东西是可以yy出来的吧..对行建线段树,再对列建线段树维护行的信息,注意打标记的位置,和返回的时候一定要记得统计上标记.开4倍内存会MLE...Co... 查看详情
bzoj1513[poi2006]tet-tetris3d二维线段树
【BZOJ1513】[POI2006]Tet-Tetris3DDescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的... 查看详情
bzoj1511:[poi2006]okr-periodsofwordskmp(代码片段)
n-ne[n]是n的最长循环节长度，其实就是n-最短前缀=后缀长度然后我们要求最短循环节，其实就是ne一直往前跳，跳到不能跳为止，这时的n-ne[n]就是n的最短循环节长度#include<iostream>#include<cstdio>usingnamespacestd;constintN=1000005;in... 查看详情
bzoj1513[poi2006]tet-tetris3d(代码片段)
二维线段树板子，注意标记永久化。1#include<bits/stdc++.h>2usingnamespacestd;3intans,A,B,n,ql,qr,qd,qu;4structQuerx56intv[3005],tag[3005];7voidchange(intk,intl,intr,intL,intR,intw)89v[k]=max(v[k],w);10if(l==L&a 查看详情
bzoj1520[poi2006]szk-schools费用流
题目描述输入输出如果有可行解,输出最小代价,否则输出NIE.样例输入5112311513255415103331样例输出9题解费用流设xi表示学生，yi表示编号，那么S->xi，容量为1，费用为0；xi->能够使得xi接受的yj，容量为1，费用为按照题目中计算... 查看详情
bzoj1513[poi2006]tet-tetris3d二维线段树
题目链接BZOJ1513题解真正地理解了一波线段树标记永久化的姿势每个节点维护两个值\(v\)和\(tag\)\(v\)代表儿子中的最值\(tag\)代表未下传的最值显然节点的区间大于等于\(v\)的实际区间而\(tag\)的区间包含节点的区间我们在修改的时... 查看详情
bzoj1513:[poi2006]tet-tetris3d
DescriptionTask:Tetris3D"Tetris"游戏的作者决定做一个新的游戏,一个三维的版本,在里面很多立方体落在平面板,一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止.作者想改变一下游戏的目的使得它更大众化,在新游戏... 查看详情
bzoj1513[poi2006]tet-tetris3d（二维线段树）
【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1513 【题目大意】 一个立方体开始落下直到碰上一个以前落下的立方体或者落地即停止. 你将知道落下的立方体信息以及位置, 你的任务就是回答所有立方... 查看详情
bzoj1511[poi2006]okr-periodsofwordskmp-next数组
原文地址：http://www.cnblogs.com/GXZlegend/p/6827027.html题目描述一个串是有限个小写字符的序列,特别的,一个空序列也可以是一个串.一个串P是串A的前缀,当且仅当存在串B,使得A=PB.如果PA并且P不是一个空串,那么我们说P是A的一个proper前缀... 查看详情
[poi2006]ork-ploughing
[POI2006]ORK-Ploughinghttps://www.luogu.org/problemnew/show/P3444题目描述(Byteasar)想耕种他那块矩形的田,他每次能耕种矩形的一边(上下左右都行),在他每次耕完后,剩下的田也一定是矩形,每块小区域边长为(1),耕地的长宽分别为(m)和(n),不幸的是(... 查看详情
bzoj2428:[haoi2006]均分数据
二次联通门: BZOJ2428:[HAOI2006]均分数据 /*BZOJ2428:[HAOI2006]均分数据模拟退火初体验完全随机化算法估计对我这种非酋来说的话估计是用处不大了吧23333*/#include<cstdio>#include<iostream>#include<cstdlib>#incl 查看详情
[bzoj2527][poi2011]meteors
2527:[Poi2011]MeteorsTimeLimit:60Sec MemoryLimit:128MBSubmit:1807 Solved:646[Submit][Status][Discuss]DescriptionByteotianInterstellarUnion(BIU)hasrecentlydiscoveredanewplanetinan 查看详情
bzoj2213[poi2011]differencedp
【BZOJ2213】[Poi2011]DifferenceDescriptionAwordconsistingoflower-caselettersoftheEnglishalphabet(‘a‘-‘z‘)isgiven.Wewouldliketochooseanon-emptycontiguous(i.e.one-piece)fragmentofthewordsoastomaximisethed 查看详情
[poi2006]okr-periodsofwords(代码片段)
---恢复内容开始---题目描述Astringisafinitesequenceoflower-case(non-capital)lettersoftheEnglishalphabet.Particularly,itmaybeanemptysequence,i.e.asequenceof0letters.ByA=BCwedenotesthatAisastringobtainedbyconcaten 查看详情