常用算法模板

• 前言
• 小技巧
• • 快读快输
• 数据结构
• • 手写循环队列
  • 手写栈
  • 手写堆
  • 并查集
  • 树状数组
  • 线段树
  • 树套树
  • 主席树
  • 莫队
  • LCA
  • 普通平衡树
  • 笛卡尔树
  • Splay
• 数学
• • 素数
  • • 判断素数
    • 筛素数
  • 求最大公约数
  • 快速乘
  • 快速幂
  • 矩阵快速幂
  • 高斯消元
  • 扩展欧几里得
  • 中国剩余定理
  • 扩展中国剩余定理
  • 大素数判定
  • 卢卡斯定理
  • 扩展卢卡斯定理
  • 乘法逆元
  • • 线性递推
    • 费马小定理(p为质数)
    • 扩展欧几里得
  • 质因数分解
  • 求欧拉函数
  • 莫比乌斯反演
  • 杜教筛
• 字符串
• • Manacher
  • 字典树
  • KMP
  • AC自动机
  • 回文自动机
• 图论
• • 链式向前星
  • 拓扑排序
  • 最短路
  • • Floyd
    • Dijkstra
    • Bellman-ford
    • SPFA
  • 最小生成树
  • • Kruskal
    • Prim
  • 欧拉路和欧拉回路
  • 无向图连通性
  • • 割点
    • 双联通分量
  • 缩点
  • 基环树
  • 二分图
  • 二分图判定
  • • 二分图最大匹配（匈牙利算法）
  • 最大流
  • • Edmonds-Karp
    • Dinic
    • ISAP
  • 费用流
• 最后

前言

临近年末，给大家整理了一些常用模板。
其中动态规划，搜索这类题我认为它没有固定的模板(正规竞赛很少考裸的背包这种吧)，所以没写。
模板大多来自于各大知名OJ的题解，也有部分来自别人的博客，少数是博主自己写的。

小技巧

快读快输

#define ll long long
ll read(){ll f=1,r=0;char ch;do ch=getchar(); while(!isdigit(ch) && ch!='-');if(ch=='-') f=-1,ch=getchar();do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));return r*f;
}
void write(ll X) {if(X < 0) putchar('-'),X=-X;if(X>9) write(X/10); putchar(X%10+'0'); 
}

数据结构

手写循环队列

struct myqueue{int data[N];int head, rear;bool init(){             //初始化head = rear = 0; return true;}int size(){ return (rear - head + N) % N;}       //返回队列长度        bool empty(){               //判断队列是否为空if(size()==0) return true;else          return false;}bool push(int e){           //队尾插入新元素。if((rear + 1) % N == head ) return false;    //队列满data[rear] = e;rear = (rear + 1) % N;return true;}bool pop(int &e){           //删除队头元素，并返回它if(head == rear) return false;       //队列空e = data[head];head = (head + 1) % N;return true;}int front(){  return data[head]; }         //返回队首，但是不删除        
}Q;

手写栈

struct mystack{int a[N];                            //存放栈元素int t = 0;                            //栈顶位置void push(int x){ a[++t] = x; }      //送入栈int top()       { return a[t]; }     //返回栈顶元素void pop()       { t--;         }     //弹出栈顶int empty()      { return t==0?1:0;}  //返回1表示空
}st;

手写堆

const int N = 1e6 + 5;
int heap[N], len=0;                 //len记录当前二叉树的长度
void push(int x) {                  //上浮，插入新元素heap[++len] = x;int i = len;while (i > 1 && heap[i] < heap[i/2]){  swap(heap[i], heap[i/2]);   i = i/2;  	}
}
void pop() {                         //下沉，删除堆头，调整堆heap[1] = heap[len--];           //根结点替换为最后一个结点，然后结点数量减1int i = 1;while ( 2*i <= len) {            //至少有左儿子int son = 2*i;                //左儿子if (son < len && heap[son + 1] < heap[son])  son++;                    //son                   //与小的儿子交换swap(heap[son], heap[i]); i = son;                 //下沉到儿子处}else break;                  //如果不比儿子小，就停止下沉}
}

并查集

const int N = 1050;
int s[N];
void init_set(){                        //初始化for(int i = 1; i <= N; i++)   s[i] = i;
}
int find_set(int x){                    //查找return x==s[x]? x:find_set(s[x]);
}
void merge_set(int x, int y){           //合并x = find_set(x);   y = find_set(y);if(x != y)    s[x] = s[y];          //把x合并到y上，y的根成为x的根
}

树状数组

const int N = 1000;
#define lowbit(x)  ((x) & - (x))
int tree[N]={0};
void update(int x, int d) {   //单点修改：修改元素a[x],  a[x] = a[x] + dwhile(x <= N) {tree[x] += d;x += lowbit(x);}
}
int sum(int x) {             //查询前缀和：返回前缀和sum = a[1] + a[2] +... + a[x]int ans = 0;while(x > 0){ans += tree[x];x -= lowbit(x);}return ans;
}

线段树

区间求和，区间修改

const int N = 1e5 + 10;
ll a[N];        //记录数列的元素，从a[1]开始
ll tree[N<<2];  //tree[i]：第i个结点的值，表示一个线段区间的值，例如最值、区间和
ll tag[N<<2];   //tag[i]：第i个结点的lazy-tag，统一记录这个区间的修改
ll ls(ll p){ return p<<1;  }           //定位左儿子：p*2
ll rs(ll p){ return p<<1|1;}           //定位右儿子：p*2 + 1
void push_up(ll p){                    //从下往上传递区间值tree[p] = tree[ls(p)] + tree[rs(p)]; 
}
void build(ll p,ll pl,ll pr){    //建树。p是结点编号，它指向区间[pl, pr]tag[p] = 0;                         //lazy-tag标记if(pl==pr){tree[p]=a[pl]; return;}  //最底层的叶子，赋值    ll mid = (pl+pr) >> 1;              //分治：折半build(ls(p),pl,mid);                //左儿子build(rs(p),mid+1,pr);              //右儿子push_up(p);                         //从下往上传递区间值
} 
void addtag(ll p,ll pl,ll pr,ll d){     //给结点p打tag标记，并更新treetag[p] += d;                        //打上tag标记tree[p] += d*(pr-pl+1);             //计算新的tree
}
void push_down(ll p,ll pl,ll pr){       //不能覆盖时，把tag传给子树if(tag[p]){                         //有tag标记，这是以前做区间修改时留下的ll mid = (pl+pr)>>1; addtag(ls(p),pl,mid,tag[p]);    //把tag标记传给左子树addtag(rs(p),mid+1,pr,tag[p]);  //把tag标记传给右子树tag[p]=0;                       //p自己的tag被传走了，归0}
}
void update(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改：把[L, R]内每个元素加上dif(L<=pl && pr<=R){       //完全覆盖，直接返回这个结点，它的子树不用再深入了    addtag(p, pl, pr,d);  //给结点p打tag标记，下一次区间修改到p时会用到return;                    }push_down(p,pl,pr);                 //如果不能覆盖，把tag传给子树ll mid=(pl+pr)>>1;if(L<=mid) update(L,R,ls(p),pl,mid,d);    //递归左子树if(R>mid)  update(L,R,rs(p),mid+1,pr,d);  //递归右子树push_up(p);                               //更新
}
ll query(ll L,ll R,ll p,ll pl,ll pr){//查询区间[L,R]；p是当前结点（线段）的编号，[pl,pr]是结点p表示的线段区间if(pl>=L && R >= pr) return tree[p];       //完全覆盖，直接返回push_down(p,pl,pr);                        //不能覆盖，递归子树ll res=0;ll mid = (pl+pr)>>1;if(L<=mid) res+=query(L,R,ls(p),pl,mid);   //左子结点有重叠if(R>mid)  res+=query(L,R,rs(p),mid+1,pr); //右子结点有重叠return res;
}

树套树

int ls(int p){ return p<<1;  }    
int rs(int p){ return p<<1|1;} 
int n=1000, s[1005][4005];      //s[i][j]：身高区间i，活泼区间j的最大缘分
void subBuild(int xp, int p, int pl, int pr) {  //建立第二维线段树：活泼度线段树s[xp][p] = -1;if(pl == pr) return;int mid=(pl+pr)>>1;subBuild(xp, ls(p), pl, mid);subBuild(xp, rs(p), mid + 1, pr);    
}
void build(int p,int pl, int pr) {              //建立第一维线段树：身高线段树subBuild(p, 1, 0, n);if(pl == pr) return;int mid=(pl+pr)>>1;build(ls(p),pl, mid);build(rs(p),mid + 1, pr);    
}
void subUpdate(int xp, int y, int c, int p, int pl, int pr) {//更新第二维线段树if(pl == pr && pl == y) s[xp][p] = max(s[xp][p], c);else {int mid=(pl+pr)>>1;if(y <= mid) subUpdate(xp, y, c, ls(p), pl, mid);else subUpdate(xp, y, c, rs(p), mid + 1, pr);s[xp][p] = max(s[xp][ls(p)], s[xp][rs(p)]);}
}
void update(int x, int y, int c, int p, int pl, int pr){ //更新第一维线段树：身高xsubUpdate(p, y, c, 1, 0, n);                         //更新第二维线段树：活泼度yif(pl != pr) {int mid=(pl+pr)>>1;if(x <= mid) update(x, y, c, ls(p), pl, mid);else update(x, y, c, rs(p), mid + 1, pr);}
}
int subQuery(int xp, int yL, int yR, int p, int pl, int pr) { //查询第二维线段树if(yL <= pl && pr <= yR) return s[xp][p];else {int mid=(pl+pr)>>1;int res = -1;if(yL <= mid) res = subQuery(xp, yL, yR, ls(p), pl, mid);if(yR >  mid) res = max(res, subQuery(xp, yL, yR, rs(p), mid + 1, pr));return res;}
}
int query(int xL, int xR, int yL, int yR, int p, int pl, int pr) {//查询第一维线段树if(xL <= pl && pr <= xR) return subQuery(p, yL, yR, 1, 0, n);  //满足身高区间时，查询活泼度区间else {                             //当前结点不满足身高区间int mid = (pl+pr)>>1;int res = -1;if(xL <= mid) res = query(xL, xR, yL, yR, ls(p), pl, mid);if(xR >  mid) res = max(res, query(xL, xR, yL, yR, rs(p), mid + 1, pr));return res;}
}

主席树

const int N = 200010;
int cnt = 0;        //用cnt标记可以使用的新结点
int a[N], b[N], root[N]; //a[]是原数组,b[]是排序后数组，root[i]记录第i棵线段树的根结点编号
struct{             //定义结点
int L, R, sum;  //L左儿子, R右儿子，sum[i]是结点i的权值（即图中圆圈内的数字）
}tree[N<<5];        //  <<4是乘16倍，不够用；<<5差不多够用   
int build(int pl, int pr){        //初始化一棵空树，实际上无必要int rt = ++ cnt;              //cnt为当前结点编号tree[rt].sum = 0;int mid=(pl+pr)>>1;if (pl < pr){tree[rt].L = build(pl, mid);tree[rt].R = build(mid+1, pr);}return rt;      //返回当前结点的编号
}
int update(int pre, int pl, int pr, int x){   //建一棵只有logn个结点的新线段树int rt = ++cnt;           //新的结点，下面动态开点tree[rt].L = tree[pre].L; //该结点的左右儿子初始化为前一棵树相同位置结点的左右儿子tree[rt].R = tree[pre].R; tree[rt].sum = tree[pre].sum + 1;  //插了1个数，在前一棵树的相同结点加1int mid = (pl+pr)>>1;if (pl < pr){            //从根结点往下建logn个结点if (x <= mid)        //x出现在左子树，修改左子树 tree[rt].L = update(tree[pre].L, pl, mid, x);else                 //x出现在右子树，修改右子树tree[rt].R = update(tree[pre].R, mid+1, pr, x);}return rt;               //返回当前分配使用的新结点的编号
}
int query(int u, int v, int pl, int pr, int k){    //查询区间[u,v]第k小if (pl == pr) return pl;  //到达叶子结点，找到第k小，pl是结点编号，答案是b[pl] int x = tree[tree[v].L].sum - tree[tree[u].L].sum;   //线段树相减int mid = (pl+pr)>>1;if (x >= k)     //左儿子数字大于等于k时，说明第k小的数字在左子树return query(tree[u].L, tree[v].L, pl, mid, k);else            //否则在右子树找第k-x小的数字 return query(tree[u].R, tree[v].R, mid+1, pr, k-x);
}

莫队

基础莫队

struct node{           //离线记录查询操作int L, R, k;       //k：查询操作的原始顺序
}q[N];
int pos[N];
int ans[N];
int cnt[N];            //cnt[i]: 统计数字i出现了多少次
int a[N];
bool cmp(node a, node b){if(pos[a.L] != pos[b.L])              //按L所在的块排序，如果块相等，再按R排序return pos[a.L] < pos[b.L];if(pos[a.L] & 1)   return a.R > b.R;  //奇偶性优化，如果删除这一句，性能差一点return a.R < b.R;     if(a.L==b.L)  return a.R < b.R;return a.L < b.L;   */
}
int ANS = 0;
void add(int x){     //扩大区间时（L左移或R右移），增加数x出现的次数cnt[a[x]]++;if(cnt[a[x]]==1)  ANS++;     //这个元素第1次出现
}
void del(int x){     //缩小区间时（L右移或R左移），减少数x出现的次数cnt[a[x]]--;if(cnt[a[x]]==0)  ANS--;     //这个元素消失了
}

LCA

倍增

//洛谷P3379 的倍增代码
#include 
using namespace std;
const int N=500005;
struct Edge{int to, next;}edge[2*N];     //链式前向星
int head[2*N], cnt;
void init(){                             //链式前向星：初始化for(int i=0;i<2*N;++i){ edge[i].next = -1;   head[i] = -1; }cnt = 0;
}
void addedge(int u,int v){               //链式前向星：加边edge[cnt].to = v;  edge[cnt].next = head[u];  head[u] = cnt++;
} //以上是链式前向星
int fa[N][20], deep[N];
void dfs(int x,int father){        //求x的深度deep[x]和fa[x][]。father是x的父结点。deep[x] = deep[father]+1;      //深度：比父结点深度多1fa[x][0] = father;             //记录父结点for(int i=1; (1<if(deep[x]=0;i--)           //x最多跳19次：2^19 > 500005if(deep[x]-(1<=deep[y])  //如果x跳过头了就换个小的i重跳x = fa[x][i];            //如果x还没跳到y的层，就更新x继续跳if(x==y)  return x;              //y就是x的祖先//（2）x和y同步往上跳，找到LCAfor(int i=19;i>=0;i--)           //如果祖先相等，说明跳过头了，换个小的i重跳if(fa[x][i]!=fa[y][i]){      //如果祖先不等，就更新x、y继续跳x = fa[x][i];   y = fa[y][i];}return fa[x][0];                 //最后x位于LCA的下一层，父结点fa[x][0]就是LCA
}
int main(){    init();                          //初始化链式前向星int n,m,root;  scanf("%d%d%d",&n,&m,&root); for(int i=1;i            //读一棵树，用链式前向星存储int u,v;       scanf("%d%d",&u,&v); addedge(u,v);  addedge(v,u);}dfs(root,0);                      //计算每个结点的深度并预处理fa[][]数组while(m--){int a,b;   scanf("%d%d",&a,&b); printf("%d\n", LCA(a,b));}return 0;
}

Tarjan求LCA

#include
using namespace std;
const int MAXN = 5e5+ 10;
int fa[MAXN], head[MAXN], head_ask[MAXN], cnt, cnt_ask, ans[MAXN];
bool vis[MAXN];
int n, m, s;
struct Edge{int to, dis, next;int num;
}edge[MAXN << 1], ask[MAXN << 1]; 
void add_edge(int u, int v, int dis) {edge[++cnt].to = v;edge[cnt].next = head[u];head[u] = cnt;
}
void add_ask(int x, int y, int num) { //num 第几个查询ask[++cnt_ask].to = y;ask[cnt_ask].num = num;	//第几个查询 ask[cnt_ask].next = head_ask[x];head_ask[x] = cnt_ask;
}
int find(int x) {	//并查集 return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void init() {cnt = 1;cnt_ask = 1;memset(vis, 0, sizeof(vis));fa[n] = n;
}
void Tarjan(int x) {vis[x] = true;for(int i = head[x]; i ; i = edge[i].next) {int to = edge[i].to;if( !vis[to] ) {Tarjan(to);fa[to] = x;}}for(int i = head_ask[x]; i; i = ask[i].next) {int to = ask[i].to;if( vis[to] ){ ans[ask[i].num] = find(to);}}
}
int main () {ios::sync_with_stdio(0);cin.tie(0);cin >> n >> m >> s;int x, y;init();for(int i = 1; i < n; ++i) {fa[i] = i;cin >> x >> y;add_edge(x, y, 0);add_edge(y, x, 0);}for(int i = 1; i <= m; ++i) {cin >> x >> y;add_ask(x, y, i);add_ask(y, x, i);} Tarjan(s);	 for(int i = 1; i <= m; ++i) {cout << ans[i] << endl;}
} 

普通平衡树

const int N = 1e6+10;
const double alpha = 0.75;  //不平衡率。一般用alpha来表示
struct Node{int ls,rs; //左右儿子int val;   //结点存的数字int tot;   //当前子树占用的空间数量，包括实际存储的结点和被标记删去的点int size;  //子树上实际存储数字的数量int del;   //=1表示这个结点存有数字，=0表示这个点存的数字被删了
}t[N];
int order[N],cnt; //order[]记录拍扁后的结果，即那些存有数字的结点。cnt是数量
int tree_stack[N],top = 0;  //用一个栈来回收和分配可用的结点
int root = 0;               //根结点，注意重建过程中根结点会变化
void inorder(int u){        //中序遍历，“拍平”摧毁这棵子树if(!u)  return;         //已经到达叶子，退出inorder(t[u].ls);       //先遍历左子树if(t[u].del)  order[++cnt] = u;      //如果该结点存有数字，读取它else          tree_stack[++top] = u; //回收该结点，等待重新分配使用inorder(t[u].rs);       //再遍历右子树
}
void Initnode(int u){       //重置结点的参数t[u].ls = t[u].rs = 0;t[u].size = t[u].tot = t[u].del = 1;
}
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size + 1;t[u].tot = t[t[u].ls].tot + t[t[u].rs].tot + 1;
}
//int rebuild_num=0;                      //测试：统计重建次数
void build(int l,int r,int &u){           //把拍扁的子树拎起来，重建
//  rebuild_num++;                        //测试：统计重建次数int mid = (l + r) >> 1;               //新的根设为中点，使重构出的树尽量平衡u = order[mid];if(l == r){Initnode(u); return;}      //如果是叶子，重置后返回if(l < mid)  build(l,mid - 1,t[u].ls);//重构左子树if(l == mid) t[u].ls = 0;             //注意这里，不要漏了build(mid + 1,r,t[u].rs);             //重构右子树Update(u);                            //更新
}
void rebuild(int &u){                     //重建。注意是&ucnt = 0;inorder(u);                           //先拍平摧毁if(cnt)   build(1,cnt,u);             //再拎起，重建树else      u = 0;                      //特判该子树为空的情况
}
bool notbalance(int u){                   //判断子树u是否平衡if((double)t[u].size*alpha <=(double)max(t[t[u].ls].size,t[t[u].rs].size))return true;                      //不平衡了return false;                         //还是平衡的
}
void Insert(int &u,int x){                //插入数字x。注意是&u，传回了新的uif(!u){                               //如果结点u为空，直接将x插到这里u = tree_stack[top--];            //从栈顶拿出可用的空结点t[u].val = x;                     //结点赋值Initnode(u);                      //其他参数初始化return;}t[u].size++;t[u].tot++;if(t[u].val >= x)  Insert(t[u].ls,x);  //插到右子树else               Insert(t[u].rs,x);  //插到左子树if(notbalance(u))  rebuild(u);         //如果不平衡了，重建这棵子树
}
int Rank(int u,int x){                     //排名，x是第几名if(u==0)	   return 0;if(x>t[u].val) return t[t[u].ls].size+ t[u].del + Rank(t[u].rs, x);return Rank(t[u].ls,x);
}
int kth(int k){                            //第k大数是几?int u = root;while(u){if(t[u].del && t[t[u].ls].size + 1 == k) return t[u].val;else if(t[t[u].ls].size >= k)  u = t[u].ls;else{k -= t[t[u].ls].size + t[u].del;u = t[u].rs;}}return t[u].val;
}
void Del_k(int &u,int k){       //删除排名为k的数t[u].size--;                //要删除的数肯定在这棵子树中，size减1if(t[u].del && t[t[u].ls].size + 1 == k){t[u].del = 0;            //del=0表示这个点u被删除了，但是还保留位置return;}if(t[t[u].ls].size + t[u].del >= k)  Del_k(t[u].ls,k); //在左子树上else   Del_k(t[u].rs,k - t[t[u].ls].size - t[u].del);  //在右子树上
}
void Del(int x){                 //删除值为k的数Del_k(root,Rank(root,x)+1);  //先找x的排名，然后用Del_k()删除if(t[root].tot * alpha >= t[root].size)rebuild(root);           //如果子树上被删除的结点太多，就重构
}

笛卡尔树

const int N = 50005;
const int INF = 0x7fffffff;
struct Node{char s[100];   int ls,rs,fa,pri;friend bool operator<(const Node& a,const Node& b){return strcmp(a.s,b.s)<0;}
}t[N];
void buildtree(int n){         //不用栈，直接查最右链for(int i=1;i<=n;i++){int pos = i-1;         //从前一个结点开始比较，前一个结点在最右链的末端while(t[pos].pri < t[i].pri) pos = t[pos].fa;  //沿着最右链一直找，直到pos的优先级比i大t[i].ls = t[pos].rs;   //图(4)：i是19，pos是24, 15调整为19的左儿子t[t[i].ls].fa = i;     //图(4)：15的父亲是19t[pos].rs = i;         //图(4)：24的右儿子是19t[i].fa = pos;         //图(4)：19的父亲是24}
}
void buildtree2(int n){             //用栈来辅助建树stack  ST;  ST.push(0);    //t[0]进栈，它一直在栈底for(int i=1;i<=n;i++){int pos = ST.top();while(!ST.empty() && t[pos].pri < t[i].pri){pos = t[ST.top()].fa;ST.pop();               //把比i优先级小的弹出栈}t[i].ls = t[pos].rs;t[t[i].ls].fa = i;t[pos].rs = i;t[i].fa = pos;ST.push(i);                 //每个结点都一定要进栈}
}
void inorder(int x){                //中序遍历打印if(x==0)     return;printf("(");inorder(t[x].ls);  printf("%s/%d",t[x].s,t[x].pri);  inorder(t[x].rs); printf(")");
}

Splay

const int M = 2e6+10;
int cnt, root;
struct Node{int fa,ls,rs,size; char val;}t[M];   //tree[]存树;
void Update(int u){t[u].size = t[t[u].ls].size + t[t[u].rs].size+1;}  //用于排名
char str[M]={0};                //一次输入的字符串
int build(int L,int R,int f){   //把字符串str[]建成平衡树if(L>R) return 0;int mid = (L+R)>>1;int cur = ++cnt;t[cur].fa = f;t[cur].val= str[mid];t[cur].ls = build(L,mid-1,cur);t[cur].rs = build(mid+1,R,cur);Update(cur);return cur;                 //返回新树的根
}
int get(int x){return t[t[x].fa].rs == x;} //如果u是右儿子，返回1；左儿子返回0
void rotate(int x){                        //单旋一次int f=t[x].fa, g=t[f].fa, son=get(x);  //f:父亲；g：祖父if(son==1) {                           //x是右儿子，左旋zagt[f].rs = t[x].ls;                 //图“单旋”中的结点bif(t[f].rs)  t[t[f].rs].fa = f;}else {                                 //x是左儿子，右旋zigt[f].ls = t[x].rs;if(t[f].ls)  t[t[f].ls].fa = f;}t[f].fa=x;                  //x旋为f的父结点if(son == 1) t[x].ls=f;     //左旋，f变为x的左儿子else t[x].rs=f;             //右旋，f变为x的右儿子t[x].fa = g;                //x现在是祖父的儿子if(g){                      //更新祖父的儿子if(t[g].rs==f)  t[g].rs = x;else  t[g].ls = x;}Update(f);   Update(x);
}
void splay(int x,int goal){     //goal=0,新的根是x；goal!=0,把x旋为goal的儿子if(goal == 0) root=x;while(1){int f = t[x].fa, g=t[f].fa;        //一次处理x,f,g三个点if(f == goal) break;if(g != goal) {                    //有祖父，分一字旋和之字旋两种情况if(get(x)==get(f)) rotate(f);  //一字旋，先旋f、gelse rotate(x);}               //之字旋，直接旋xrotate(x);}Update(x);
}
int kth(int k,int u){            //第k大数的位置if( k == t[t[u].ls].size + 1) return u;if( k <= t[t[u].ls].size )    return kth(k,t[u].ls);if( k >= t[t[u].ls].size + 1) return kth(k-t[t[u].ls].size-1,t[u].rs);
}
void Insert(int L,int len){                  //插入一段区间int x = kth(L,root), y = kth(L+1,root);  //x:第L个数的位置，y:第L+1个数的位置splay(x,0);   splay(y,x);                //分裂//先把x旋到根，然后把y旋到x的儿子，此时y是x的右儿子，且y的左儿子为空t[y].ls = build(1,len,y);                //合并：建一棵树，挂到y的左儿子上Update(y);    Update(x);
}
void del(int L,int R){             //删除区间[L+1,R]int x=kth(L,root), y=kth(R+1,root);splay(x,0); splay(y,x);        //y是x的右儿子，y的左儿子是待删除的区间t[y].ls=0;                 //剪断左子树，等于直接删除。这里为了简单，没有释放空间Update(y);    Update(x);
}
void inorder(int u){           //中序遍历if(u==0) return;inorder(t[u].ls);cout<

bool isprime(int x){if(x <= 1) return 0;for(int i=2;i*i<=x;i++)if(x%i == 0) return 0;return 1;
}

int n,cnt=0;//cnt是素数个数
int prime[10001];//存素数
cin >> n;//n表示范围
memset(prime,1,sizeof(prime);//先全定为素数
prime[0] = 0;
prime[1] = 0;//特判
for(int i=2;i//如果没被修改过就一定是素数prime[++cnt]=i;//前面的已经遍历过了，可以节约无用空间来存素数for(int k=i*i; k

int n,cnt=0;
int prime[10001];//存素数
bool vis[10001];//保证不做素数的倍数
cin >> n;
memset(prime,0,sizeof(prime);
memset(vis,0,sizeof(vis);
for(int i=2;i<=n;i++){if(!vis[i])//不是目前找到的素数的倍数prime[cnt++] = i;//找到素数for(int j=0;jvis[i*prime[j]] = true;//找到素数的倍数不访问if(i % prime[j] == 0) break;}
}​

#define ll long long
ll gcd(ll a,ll b){if(b == 0) return a;return gcd(b,a%b);
}

ll mul(ll a,ll b,ll m){     //乘法取模：a*b mod ma = a%m;                //先取模，非常重要，能在一定程度上防止第10行a+a溢出b = b%m;ll res = 0;while(b>0){             //递归思想if(b&1) res=(res+a)% m;  //用b&1判断b的奇偶a=(a+a)% m;              //需要保证a+a=2a不能溢出，否则答案错误b>>=1;}return res;
}

typedef long long ll;                      
ll fastPow(ll a, ll n, ll mod){ll ans = 1;a %= mod;                              止下面的a*a越界while(n) {if(n & 1)   ans = (ans*a) % mod;   //取模 a = (a*a) % mod;                   //取模n >>= 1;}return ans;
}

struct matrix{ int m[N][N]; };     //定义矩阵，常数N是矩阵的行数和列数
matrix operator * (const matrix& a, const matrix& b){   //重载*为矩阵乘法。注意constmatrix c;   memset(c.m, 0, sizeof(c.m));  //清零for(int i=0; i  //矩阵快速幂，代码和普通快速幂几乎一样matrix ans;   memset(ans.m,0,sizeof(ans.m));for(int i=0;iif(n&1) ans = ans * a;       //不能简写为ans *= a，这里的*重载了a = a * a;n>>=1;}return ans;
}

#include
using namespace std;
double a[105][105];
double eps = 1e-7;
int main(){int n; scanf("%d",&n);for(int i=1;i<=n;++i)for(int j=1;j<=n+1;++j) 	scanf("%lf",&a[i][j]);for(int i=1;i<=n;++i){            //枚举列int max=i;for(int j=i+1;j<=n;++j)      //选出该列最大系数，真实目的是选一个非0系数if(fabs(a[j][i])>fabs(a[max][i]))   max=j;for(int j=1;j<=n+1;++j) swap(a[i][j],a[max][j]); //移到前面if(fabs(a[i][i]) < eps){     //对角线上的主元系数等于0,说明没有唯一解puts("No Solution");return 0;}for(int j=n+1;j>=1;j--)	  a[i][j]= a[i][j]/a[i][i]; //把这一行的主元系数变为1for(int j=1;j<=n;++j){       //消去主元所在列的其他行的主元if(j!=i)	{double temp=a[j][i]/a[i][i];for(int k=1;k<=n+1;++k)  a[j][k] -= a[i][k]*temp;}}}for(int i=1;i<=n;++i)	printf("%.2f\n",a[i][n+1]); //最后得到简化阶梯矩阵return 0;
}

#define ll long long
ll extend_gcd(ll a,ll b,ll &x,ll &y){if(b == 0){ x=1; y=0; return a;}ll d = extend_gcd(b,a%b,y,x);y -= a/b * x;return d;
}

#include
#define ll long long
using namespace std;
const int MAX = 12;
ll n,ans;
ll read(){ll f=1,r=0;char ch;do ch=getchar(); while(!isdigit(ch) && ch!='-');if(ch=='-') f=-1,ch=getchar();do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));return r*f;
}
void write(ll X) {if(X < 0) putchar('-'),X=-X;if(X>9) write(X/10); putchar(X%10+'0'); 
}void exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return;}exgcd(b,a%b,x,y);ll z=x;x=y;y=z-(a/b)*y;
}
ll a[MAX],b[MAX],M[MAX],t[MAX],s=1,y;
int main(){n = read();for(int i=1;i<=n;i++){a[i] = read();b[i] = read();s *= a[i];}for(int i=1;i<=n;i++) M[i]=s/a[i];for(int i=1;i<=n;i++){exgcd(M[i],a[i],t[i],y);t[i] = (t[i]%a[i]+a[i])%a[i];}for(int i=1;i<=n;i++) ans+=b[i]*M[i]*t[i]%s;write(ans%s);return 0;
}

#include
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
ll ai[N], mi[N];
ll mul(ll a,ll b,ll m){                 //乘法取模：a*b % mll res=0;while(b>0){if(b&1) res=(res+a) % m;a=(a+a) % m;b>>=1;}return res;
}
ll extend_gcd(ll a,ll b,ll &x,ll &y){   //扩展欧几里得if(b == 0){ x=1; y=0; return a;}ll d = extend_gcd(b,a%b,y,x);y -= a/b * x;return d;
}
ll excrt(){                              //求解同余方程组，返回最小正整数解ll x,y;ll m1 = mi[1], a1 = ai[1];           //第1个等式ll ans = 0;for(int i=2;i<=n;i++){               //合并每2个等式       ll a2 = ai[i], m2 = mi[i];       // 第2个等式 //合并为：aX + bY = c      ll a = m1, b = m2, c = (a2 - a1%m2 + m2) % m2;//下面求解 aX + bY = cll d = extend_gcd(a,b,x,y);  //用扩展欧几里得求x0if(c%d != 0) return -1;      //无解x = mul(x,c/d,b/d);          //aX + bY = c 的特解t，最小值           ans = a1 + x* m1;            //代回原第1个等式，求得特解x'm1 = m2/d*m1;                //先除再乘，避免越界。合并后的新m1ans = (ans%m1 + m1) % m1;    //最小正整数解a1 = ans;                    //合并后的新a1}return ans;
}
int main(){scanf("%d", &n);for(int i=1;i<=n;++i)  scanf("%lld%lld",&mi[i],&ai[i]);printf("%lld",excrt());return 0;
}

inline LL quick_mul(LL a,LL b,LL m) //快速乘 
{ll ans = 0;a %= m;b %= m;while (b) {if (b & 1) {ans = (ans + a) % m;}a = (a + a) % m;b >>= 1;}return ans;
}LL quick_pow(LL a,LL b,LL m) //快速幂 
{LL res=1;a%=m;while(b){if(b&1) res=quick_mul(res,a,m);a=quick_mul(a,a,m);b>>=1;}return res;
}
bool Miller_rabin(LL n,int num)
{
//先将特殊情况判断一下if(n==2||n==3) return true;if(n%2==0||n==1) return false;srand((unsigned)time(NULL)); //为接下来a的随机取值用 LL d=n-1;int s=0;while(!(d&1)) s++,d>>=1;//若d的二进制的最后一位不是1，则说明d还是偶数 for(int i=0;iLL a=rand()%(n-2)+2;//2~n-1;LL x=quick_pow(a,d,n), y=0;for(int j=0;jy=quick_mul(x,x,n);//先平方 if(y==1&&x!=1&&x!=(n-1)) return false;//验证二次探测原理 x=y;}if(y!=1) return false;//不满足费马小定理，那就肯定不是质数}return true;
}

#include 
#define ll long long
using namespace std;
ll p;
long long read(){long long f=1,r=0;char ch;do ch=getchar(); while(!isdigit(ch) && ch!='-');if(ch=='-') f=-1,ch=getchar();do r=r*10+ch-48,ch=getchar(); while(isdigit(ch));return r*f;
}
void write(long long X) {if(X < 0) putchar('-'),X=-X;if(X>9) write(X/10); putchar(X%10+'0');
}
inline ll power(ll x,ll mod){ll ans = 1;for(;mod;mod>>=1){//快速幂 if(mod & 1)ans = x*ans%p;x = x*x%p;}return ans;
} 
inline ll inv(ll x){return power(x,p-2);//费马小定理求逆元 
}
inline ll C(ll n,ll m){ll ans = 1;for(int i=n;i>=n-m+1;i--)ans = ans*i%p;ll s = 1;for(int i=2;i<=m;i++)s = s*i%p;return ans*inv(s)%p;
}
inline ll lucas(ll n,ll m){return C(n%p,m%p)*C(n/p,m/p)%p;
}
int main(){int T = read();while(T--){ll n = read(); ll m = read(); p = read();write(lucas(n+m,n)); putchar('\n');}return 0;
}

#include
#include
using namespace std;
long long n,m,p,cnt/*个数*/,pr[1010]/*质数*/,al[1010]/*指数*/;
void exgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里得算法
{if (!b) return (void)(x=1,y=0);exgcd(b,a%b,x,y);long long tmp=x;x=y;y=tmp-a/b*y;
}
long long ny(long long a,long long p)//逆元
{long long x,y;exgcd(a,p,x,y);return (x+p)%p;
}
long long POW(long long a,long long b,long long p)//快速幂
{long long t=1;a%=p;for(;b;b>>=1){if(b&1) t=t*a%p;a=a*a%p;}return t;
}
long long fac(long long n,long long p,long long ppa)//计算n!
{if (n==0) return 1;long long cir=1/*循环节*/,rem=1/*余数*/;for (long long i=1;i<=ppa;i++) if(i%p) cir=cir*i%ppa;cir=POW(cir,n/ppa,ppa);for(long long i=ppa*(n/ppa);i<=n;i++) if(i%p) rem=rem*(i%ppa)%ppa;return fac(n/p,p,ppa)*cir%ppa*rem%ppa;
}
long long sum_fac(long long n,long long p)//n!中p的个数
{return nlong long fz=fac(n,p,ppa),fm1=ny(fac(m,p,ppa),ppa),fm2=ny(fac(n-m,p,ppa),ppa);long long mi=POW(p,sum_fac(n,p)-sum_fac(m,p)-sum_fac(n-m,p),ppa);return fz*fm1%ppa*fm2%ppa*mi%ppa;
}
void pfd(long long n,long long m)//分解p
{long long P=p;for(long long i=2;i*i<=p;i++){if(!(P%i)){long long ppa=1;while(!(P%i)) ppa*=i,P/=i;pr[++cnt]=ppa;al[cnt]=C(n,m,i,ppa);}}if(P!=1) pr[++cnt]=P,al[cnt]=C(n,m,P,P);
}
long long crt()//中国剩余定理
{long long ans=0;for(long long i=1;i<=cnt;i++){long long M=p/pr[i],T=ny(M,pr[i]);ans=(ans+al[i]*M%p*T%p)%p;}return ans;
}
long long exlucas(long long n,long long m)//扩展卢卡斯 
{pfd(n,m);return crt();
}
int main()
{cin>>n>>m>>p;cout<

#include
#define ll long long
using namespace std;
const int MAX = 3e6+10;
ll n,p;
ll inv[MAX];
int main(){ios::sync_with_stdio(false);cin >> n >> p;inv[1] = 1;for(int i=2;i<=n;i++)inv[i] = (p-p/i)*inv[p%i]%p;for(int i=1;i<=n;i++)cout << inv[i] << "\n";return 0;
}

inline ll power(ll x,ll mod){ll ans = 1;for(;mod;mod>>=1){//快速幂 if(mod & 1)ans = x*ans%p;x = x*x%p;}return ans;
} 
inline ll inv(ll x){return power(x,p-2);//费马小定理求逆元 
}

void exgcd(long long a,long long b,long long &x,long long &y)//扩展欧几里得算法
{if (!b) return (void)(x=1,y=0);exgcd(b,a%b,x,y);long long tmp=x;x=y;y=tmp-a/b*y;
}
long long ny(long long a,long long p)//逆元
{long long x,y;exgcd(a,p,x,y);return (x+p)%p;
}

int prime[N];      //记录质数
int vis[N];        //记录最小质因子
int euler_sieve(int n){     int cnt=0;memset(vis,0,sizeof(vis));memset(prime,0,sizeof(prime));for(int i=2;i<=n;i++){               if(!vis[i]){ vis[i]=i; prime[cnt++]=i;}    //vis[]记录最小质因子for(int j=0; j       if(i*prime[j] >n)  break;       vis[i*prime[j]] = prime[j];            //vis[]记录最小质因子if(i%prime[j]==0)  break;                  }}return cnt;
}

int euler(int n){int ans = n;for(int p = 2; p*p <= n; ++ p){ //试除法：检查从2到sqrt(n)的每个数if(n%p == 0){               //能整除，p是一个因子，而且是质因子，请思考ans = ans/p*(p-1);      //求欧拉函数的通式while(n%p == 0)         //去掉这个因子的幂，并使得下一个p是质因子n /= p;             //减小了n}}if(n != 1)  ans = ans/n*(n-1);  //情况(1)：n是一个质数，没有执行上面的分解        return ans;
}

bool vis[N];
int prime[N];
int Mob[N];
void Mobius_sieve(){int cnt = 0;vis[1] = 1;Mob[1] = 1;for(int i = 2; i <= N; i++){if(!vis[i])  prime[cnt++] = i, Mob[i] = - 1;for(int j = 0; j < cnt && 1LL * prime[j] * i <= N; j++){vis[prime[j] * i] = 1;Mob[i * prime[j]] = (i % prime[j] ? -Mob[i]: 0);if(i % prime[j] == 0)  break;}}
}

#include 
using namespace std;
typedef long long ll;
const int N = 5e6+7;         //超过n^(2/3)，够大了
int prime[N];                //记录质数
bool vis[N];                 //记录是否被筛；
int mu[N];                   //莫比乌斯函数值
ll phi[N];                   //欧拉函数值
unordered_map summu;   //莫比乌斯函数前缀和
unordered_map sumphi;   //欧拉函数前缀和
void init(){                    //线性筛预计算一部分答案int cnt = 0;vis[0] = vis[1] = 1;mu[1] = phi[1] = 1;for(int i=2;iif(!vis[i]){ prime[cnt++] = i;mu[i] = -1;phi[i] = i-1;}for(int j=0;jvis[i*prime[j]] = 1; if(i%prime[j]){ mu[i*prime[j]] = -mu[i];phi[i*prime[j]] = phi[i]*phi[prime[j]];} else{mu[i*prime[j]] = 0;phi[i*prime[j]] = phi[i]*prime[j]; break;}}}for(int i=1;i       //最后，mu[]和phi[]改为记录1~N的前缀和。mu[i] += mu[i-1];phi[i] += phi[i-1];}
}
int gsum(int x){                    // g(i)的前缀和return x;
}
ll getsmu(int x){if(x < N) return mu[x];      //预计算if(summu[x]) return summu[x];   //记忆化  ll ans = 1;                     //杜教筛公式中的 1for(ll l=2,r;l<=x;l=r+1){       //用整除分块计算杜教筛公式r = x/(x/l); ans -= (gsum(r)-gsum(l-1))*getsmu(x/l);}return summu[x] = ans/gsum(1);
}
ll getsphi(int x){if(x < N) return phi[x];if(sumphi[x]) return sumphi[x];  //记忆化，每个sumphi[x]只用算一次ll ans = x*((ll)x+1)/2;          //杜教筛公式中的 n(n+1)/2for(ll l=2,r;l<=x;l=r+1){        //用整除分块计算杜教筛公式，这里算 sqrt(x)次r = x/(x/l);ans -= (gsum(r)-gsum(l-1))*getsphi(x/l);} return sumphi[x] = ans/gsum(1);
}
int main(){  init();                          //用线性筛预计算一部分int t;	scanf("%d",&t);while(t--){ int n;  scanf("%d",&n);printf("%lld %lld\n",getsphi(n),getsmu(n));}return 0;
}

#include
using namespace std;
const int N=11000002;
int n,P[N<<1];        //P[i]: 以s[i]为中心的回文半径
char a[N],s[N<<1];
void change(){        //变换n = strlen(a);int k = 0;  s[k++]='$'; s[k++]='#';for(int i=0;is[k++]=a[i]; s[k++]='#';}  //在每个字符后面插一个#s[k++]='&';                       //首尾不一样，保证第18行的while循环不越界n = k;
}
void manacher(){int R = 0, C;for(int i=1;iif(i < R)  P[i] = min(P[(C<<1)-i],P[C]+C-i); //合并处理两种情况else       P[i] = 1;while(s[i+P[i]] == s[i-P[i]])   P[i]++;      //暴力：中心扩展法            if(P[i]+i > R){R = P[i]+i;        //更新最大RC = i;}}
}
int main(){scanf("%s",a);   change();manacher();int ans=1;for(int i=0;i

#include 
using namespace std;
const int N = 800000;
struct node{bool repeat;    //这个前缀是否重复int son[26];    //26个字母int num;        //这个前缀出现的次数
}t[N];              //trie
int cnt = 1;        //当前新分配的存储位置。把cnt=0留给根结点
void Insert(char *s){int now = 0;for(int i=0;s[i];i++){int ch=s[i]-'a';if(t[now].son[ch]==0)          //如果这个字符还没有存过t[now].son[ch] = cnt++;    //把cnt位置分配给这个字符now = t[now].son[ch];          //沿着字典树往下走t[now].num++;                  //统计这个前缀出现过多少次}
}
int Find(char *s){int now = 0;for(int i=0;s[i];i++){int ch = s[i]-'a';if(t[now].son[ch]==0) return 3; //第一个字符就找不到now = t[now].son[ch];}if(t[now].num == 0) return 3;       //这个前缀没有出现过if(t[now].repeat == false){         //第一次被点名t[now].repeat = true;return 1;}return 2;// return t[p].num;                    //若有需要，返回以s为前缀的单词的数量
}

#include 
#define ll long long
using namespace std;
const int N = 1e6+10;
int kmp[N];
int main(){string a,b;cin >> a >> b;a = " "+a; b = " " + b;int la = a.size()-1,lb = b.size()-1;for(int i=2,j=0;i<=lb;i++){while(j&&b[i]!=b[j+1]) j = kmp[j];if(b[i] == b[j+1]) j++;kmp[i] = j;} for(int i=1,j=0;i<=la;i++){while(j&&a[i]!=b[j+1]) j = kmp[j];if(a[i] == b[j+1]) j++;if(j == lb){cout << i-j+1 << "\n";j = kmp[j];}}for(int i=1;i<=lb;i++)cout << kmp[i] << " ";return 0;
}

struct Tree//字典树 
{int fail;//失配指针int vis[26];//子节点的位置int end;//标记有几个单词以这个节点结尾 
}AC[1000000];//Trie树
int cnt=0;//Trie的指针 
inline void Build(string s)
{int l=s.length();int now=0;//字典树的当前指针 for(int i=0;iif(AC[now].vis[s[i]-'a']==0)//Trie树没有这个子节点AC[now].vis[s[i]-'a']=++cnt;//构造出来now=AC[now].vis[s[i]-'a'];//向下构造 }AC[now].end+=1;//标记单词结尾 
}
void Get_fail()//构造fail指针
{queue Q;//队列 for(int i=0;i<26;++i)//第二层的fail指针提前处理一下{if(AC[0].vis[i]!=0){AC[AC[0].vis[i]].fail=0;//指向根节点Q.push(AC[0].vis[i]);//压入队列 }}while(!Q.empty())//BFS求fail指针 {int u=Q.front();Q.pop();for(int i=0;i<26;++i)//枚举所有子节点{if(AC[u].vis[i]!=0)//存在这个子节点{AC[AC[u].vis[i]].fail=AC[AC[u].fail].vis[i];//子节点的fail指针指向当前节点的//fail指针所指向的节点的相同子节点 Q.push(AC[u].vis[i]);//压入队列 }else//不存在这个子节点 AC[u].vis[i]=AC[AC[u].fail].vis[i];//当前节点的这个子节点指向当//前节点fail指针的这个子节点 }}
}
int AC_Query(string s)//AC自动机匹配
{int l=s.length();int now=0,ans=0;for(int i=0;inow=AC[now].vis[s[i]-'a'];//向下一层for(int t=now;t&&AC[t].end!=-1;t=AC[t].fail)//循环求解{ans+=AC[t].end;AC[t].end=-1;} }return ans;
}

const int MAXN = 2e6 + 5;struct Node{Node *ch[26], *fail;int len, sum;
}tr[MAXN];int n;
char s[MAXN];
int ncnt = 2;
Node *last;Node *New(int len) {tr[ncnt].len = len;tr[ncnt].fail = &tr[0];for (int i = 0; i < 26; i++) tr[ncnt].ch[i] = &tr[0];return &tr[ncnt++];
}Node *GetFail(Node *x, int pos) {while (s[pos - x->len - 1] != s[pos]) x = x->fail;return x;
}void Init() {tr[0].len = 0; tr[1].len = -1;tr[0].fail = &tr[1]; tr[1].fail = &tr[0];for (int i = 0; i < 26; i++) tr[0].ch[i] = tr[1].ch[i] = &tr[0];last = &tr[0];
}void Insert(int pos) {Node *cur = GetFail(last, pos);if (cur->ch[s[pos] - 'a'] == &tr[0]) {Node *now = New(cur->len + 2);now->fail = GetFail(cur->fail, pos)->ch[s[pos] - 'a'];now->sum = now->fail->sum + 1;cur->ch[s[pos] - 'a'] = now;}last = cur->ch[s[pos] - 'a'];
}

const int N = 1e6+5, M = 2e6+5;             //1百万个点,2百万个边
int cnt=0,head[N];                          //cnt等于其他值也行，根据题目要求赋值 
struct {int to, next, w;} edge[M];
void addedge(int u,int v,int w) {cnt++;edge[cnt].to = v;   edge[cnt].w = w;edge[cnt].next = head[u];head[u] = cnt;
}

int n,a[25],dir[30][30];           //dir[i][j]=1表示i、j是先后关系
int topo[25],vis[30],indegree[30]; //topo[]记录拓扑排序，indegree记录度，vis标记是否访问
void dfs(int z,int cnt){int i;topo[cnt]=z;                  //记录拓扑排序if(cnt==n-1) {                //所有点取完了，输出一个拓扑排序for(i=0;iif(!vis[a[i]] && dir[z][a[i]] )indegree[a[i]] --;      //把所有下属的度数减一}for(i=0;iif(!vis[a[i]] && dir[z][a[i]] )indegree[a[i]] ++;}vis[z]=0;          //恢复
}

for(int k=1; k<=n; k++)         //floyd的3重循环for(int i=1; i<=n; i++)for(int j=1; j<=n; j++)    if(dp[i][k] && dp[k][j];)dp[i][j] = 1;   

#include 
#define ll long long
using namespace std;const int N = 1e5+5,M = 2e5+5;
int n,m,s;
struct EDGE{int u,v,w,nxt;
}edge[M]; int tot,head[N];
void add(int u,int v,int w){edge[++tot].u = u; edge[tot].v = v;edge[tot].w = w; edge[tot].nxt = head[u];head[u] = tot;
}
int d[N]; bool vis[N];
priority_queue  >q;
void dijkstra(){memset(d,0x3f,sizeof(d)); d[s] = 0;q.push(make_pair(0,s));while(!q.empty()){int x = q.top().second; q.pop();if(vis[x]) continue;for(int i=head[x];i;i=edge[i].nxt){int y = edge[i].v , z = edge[i].w;if(d[x]+z < d[y]){d[y] = d[x]+z;q.push(make_pair(-d[y],y));}}vis[x] = true;}
}
int main(){ios::sync_with_stdio(false);cin >> n >> m >> s;for(int i=1;i<=m;i++){int u,v,w;cin >> u >> v >> w;add(u,v,w);}dijkstra();for(int i=1;i<=n;i++)cout << d[i] << " ";return 0;
}

const int INF = 1e6;
const int N = 105;
struct Edge { int u, v, w; } e[10005];       //边：起点u，终点v，权值w
int n, m, cnt;
int pre[N];   //记录前驱结点，用于打印路径。pre[x]=y：在最短路径上，结点x的前一个结点是y
void print_path(int s, int t) {              //打印从s到t的最短路if(s==t){ printf("%d ", s); return; }    //打印起点print_path(s, pre[t]);                   //先打印前一个点printf("%d ", t);                        //后打印当前点。最后打印的是终点t
}
void bellman(){int s=1;         //定义起点int d[N];        //d[i]记录第i个结点到起点s的最短距离for (int i=1; i<=n; i++)  d[i]=INF;    //初始化为无穷大d[s]=0;for (int k=1; k<=n; k++)               //一共有n轮操作for (int i=0; i < cnt; i++){     //检查每条边int x = e[i].u,  y = e[i].v;if (d[x] > d[y] + e[i].w){   // x通过y到达起点s：如果距离更短，更新d[x] = d[y] + e[i].w;pre[x] = y;              //如果有需要，记录路径}}printf("%d\n", d[n]);// print_path(s,n);                  //如果有需要，打印路径
}

const int N = 1e6+5, M = 2e6+5;            //1百万个点,2百万个边
int n, m;
int pre[N];                                //记录前驱结点，用于打印路径
void print_path(int s, int t) {            //打印从s到t的最短路if(s==t){ printf("%d ", s); return; }  //打印起点print_path(s, pre[t]);                 //先打印前一个点printf("%d ", t);                      //后打印当前点。最后打印的是终点t
}
int head[N],cnt;                          //链式前向星
struct {int to, next, w;}edge[M];         //存边
void init(){                               //链式前向星初始化for(int i = 0; i < N; ++i)   head[i] = -1;        //点初始化for(int i = 0; i < M; ++i)   edge[i].next = -1;   //边初始化cnt = 0;
}
void addedge(int u, int v, int w){      //前向星存边edge[cnt].to=v; edge[cnt].w=w; edge[cnt].next=head[u]; head[u]=cnt++;
}
int dis[N];            //dis[i]，从起点到点i的距离
bool inq[N];           //inq[i] = true 表示点i在队列中
int Neg[N];            //判断负环(Negative loop)
int spfa(int s) {      //返回1表示出现负环memset(Neg, 0, sizeof(Neg));Neg[s] = 1;for(int i=1; i<=n; i++) {dis[i]=INF;  inq[i]=false; }   //初始化dis[s] = 0;                    //起点到自己的距离是0queue Q;     Q.push(s);   //从s开始，s进队列inq[s] = true;                 //起点在队列中while(!Q.empty()) {int u = Q.front(); Q.pop();     //队头出队inq[u] = false;                 //u已经不在队列中for(int i=head[u]; ~i; i = edge[i].next) {  //~i也可以写成 i!=-1int v = edge[i].to, w = edge[i].w;      //v是u的第i个邻居if (dis[u]+w < dis[v]) {    //u的第i个邻居v，它借道u，到s更近dis[v] = dis[u]+w;      //更新邻居v到s的距离pre[v] = u;             //如果有需要，记录路径if(!inq[v]) {           //邻居v更新状态了，但v不在队列中，放进队列inq[v] = true;Q.push(v);Neg[v]++;                   //点v进入队列的次数if(Neg[v] > n) return 1;    //出现负环}}}}return 0;
}

#include 
using namespace std;
const int N = 5005,M = 2e5+1;
struct Edge{int u,v,w;}edge[M];       //用最简单且最省空间的结构体数组存边
bool cmp(Edge a, Edge b){ return a.w < b.w;}       //从小到大排序
int s[N];                             //并查集
int find_set(int x){                  //查询并查集，返回x的根if(x != s[x])s[x] = find_set(s[x]);         //路径压缩return s[x];
}
int n,m;                              // n个点，m条边
void kruskal(){sort(edge+1, edge+m+1, cmp);      //对边做排序for(int i=1; i<=n; i++) s[i]=i;   //并查集初始化int ans = 0, cnt=0;               //cnt: 已经加入MST的边数for(int i=1; i<=m; i++){          //贪心：逐一加入每条边if(cnt == n-1)    break;      //小优化：不要也行int e1 = find_set(edge[i].u); //边的前端点u属于哪个集？int e2 = find_set(edge[i].v); //边的后端点v属于哪个集？if(e1 == e2) continue;        //属于同一个集：产生了圈，丢弃else{                         //不属于同一个集ans += edge[i].w;         //计算MSTs[e1]= e2;                //合并cnt++;                    //统计MST中的边数}}if(cnt == n-1) cout << ans;       //n-1条边else cout << "orz";               //图不是连通的
}
int main(){cin >> n >> m;for(int i=1; i<=m; i++)  cin >> edge[i].u >> edge[i].v >> edge[i].w;kruskal();return 0;
}

#include 
using namespace std;
const int N=5005,M = 2e5+1;
struct edge{                              //记录边
int to, w;  
edge(int a,int b){ to = a, w = b;}    //赋值
};
vector G[M];
struct node {int id, dis;   //id:点；dis：边node(int a, int b){ id = a, dis = b;}  //赋值bool operator < (const node &u) const { return dis > u.dis; }
};
int n, m;
bool done[N];                //done[i]=ture: 表示点i已经在MST中
void  prim() {               //对比dijkstra: 求s到其他所有点的最短路int s = 1;               //从任意点开始，例如从1开始for(int i =1;i<=N;i++)   done[i]=false;   //初始化priority_queue q;q.push(node(s, 0));      //从s点开始处理队列int ans=0,cnt=0;while (!q.empty()) {node u = q.top();   q.pop();    //pop出距集合U最近的点uif (done[u.id])     continue;   //丢弃已经在MST中的点，有判圈的作用done[u.id] = true;              //标记ans += u.dis;cnt++;                          //统计点数for (int i = 0; i< G[u.id].size(); i++) {    //检查点u的所有邻居edge y = G[u.id][i];        //一个邻居yif (done[y.to])   continue; //丢弃已经在MST中的点q.push(node(y.to, y.w));    //扩展新的邻居，放进优先队列}}if(cnt == n) cout << ans;           //cnt=n个点。注意在kruskal代码中cnt是边数
else cout << "orz";
}
int main() {cin>>n>>m;for(int i=1; i<=m; i++) {int a,b,w;   cin>>a>>b>>w;G[a].push_back(edge(b,w));  G[b].push_back(edge(a,w));  //双向边}prim();return 0;
}

#include
using namespace std;
const int N = 55;
int degree[N];  //记录度
int G[N][N];    //存图
void euler(int u){                   //从u开始DFSfor(int v = 1; v <= 50; v++)  {  //v是u的邻居if(G[u][v]) {G[u][v]--;G[v][u]--;euler(v);cout << v << " " << u << endl;    //在euler()后打印，即回溯时打印}}
}
int main(){int t; cin >> t;int cnt = 0;while (t--) {cnt++;if(cnt != 1) cout << endl;cout << "Case #" << cnt << endl;memset(degree, 0, sizeof(degree));memset(G, 0, sizeof(G));int n;  cin >> n;int color;for(int i = 0; i < n; i++) {   //输入n条边int u, v;  cin>>u>>v;color = u;                 //记录一种颜色。测试的时候可能只出现某些颜色degree[u]++;degree[v]++;               //记录点的度G[u][v]++;G[v][u]++;                 //存图：=0不连接，=1连接，>1有重边}int ok = 1;for(int i = 1; i <= 50; i++)if(degree[i] % 2) {        //存在奇点，无欧拉路cout<<"some beads may be lost"<

#include
#define ll long long
using namespace std;ll read(){ll X = 0 ; int f = 1;char ch = getchar();while(!isdigit(ch) && ch != '-') ch = getchar();if(ch == '-'){ch = getchar();f = -1;}while(isdigit(ch)){X = (X<<1)+(X<<3)+ch-'0';ch = getchar();}return X*f;
}const int N = 2e4+10 , M = 2e5+10;
int n,m; int to[M] , nxt[M] , head[N] , tot;
inline void add(int x,int y){to[++tot] = y;nxt[tot] = head[x];head[x] = tot;
}int dfn[N] , low[N] , Num; bool cut[N];
void tarjan(int x,int rt){dfn[x] = low[x] = ++Num;int flag = 0;for(int i=head[x];i;i=nxt[i]){int y = to[i];if(!dfn[y]){tarjan(y,rt);low[x] = min(low[x],low[y]);if(dfn[x] <= low[y])flag++;}else low[x] = min(low[x],dfn[y]);}if(flag > 1) cut[x] = true;else if(flag && rt != x) cut[x] = true;
}int main(){n = read(); m = read();for(int i=1;i<=m;i++){int x = read() , y = read();add(x,y); add(y,x);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i,i);int cnt = 0;for(int i=1;i<=n;i++)if(cut[i]) cnt++;printf("%d\n",cnt);for(int i=1;i<=n;i++)if(cut[i]) printf("%d ",i);return 0;
}

#include
#include
#include
using namespace std;
const int N = 1005;
int n, m, low[N], dfn;
vector G[N];                  //存图
void dfs(int u,int fa){            //计算每个点的low值low[u]= ++dfn;for(int i=0;iint v = G[u][i];if(v == fa) continue;if(!low[v]) dfs(v,u);low[u] = min(low[u], low[v]);}
}
int tarjan(){int degree[N];                  //计算每个缩点的度数memset(degree,0,sizeof(degree));for(int i=1; i<=n; i++)         //把有相同low值的点看成一个缩点for(int j=0; jwhile(~scanf("%d%d", &n, &m)){memset(low, 0, sizeof(low));for(int i=0; i<=n; i++)   G[i].clear();for(int i=1; i<=m; i++){int a, b;  scanf("%d%d", &a, &b);G[a].push_back(b);  G[b].push_back(a);}dfn = 0;dfs(1,-1);int ans = tarjan();printf("%d\n",(ans+1)/2);}return 0;
}

#include
#define ll long long
using namespace std;ll read(){ll X = 0 ; int f = 1;char ch = getchar();while(!isdigit(ch) && ch != '-') ch = getchar();if(ch == '-'){ch = getchar();f = -1;}while(isdigit(ch)){X = (X<<1)+(X<<3)+ch-'0';ch = getchar();}return X*f;
}const int N = 1e4+10 , M = 1e5+10;
int n,m; 
int a[N];class Graph{private:int tot;public:int head[N],ver[M],nxt[M];inline void add(int u,int v){ver[++tot] = v;nxt[tot] = head[u];head[u] = tot;}
}c1,c2;int dfn[N],low[N],Num,fa[N],val[N],Sum;
int stk[N],top;bool ins[N];
void tarjan(int x){dfn[x] = low[x] = ++Num;stk[++top] = x; ins[x] = true;for(int i=c1.head[x];i;i=c1.nxt[i]){int y = c1.ver[i];if(!dfn[y]){tarjan(y);low[x] = min(low[x],low[y]);}else if(ins[y])low[x] = min(low[x],dfn[y]);}if(low[x] == dfn[x]){Sum++;do{val[Sum] += a[stk[top]];ins[stk[top]] = false;fa[stk[top]] = Sum;}while(stk[top--] != x);}
}int main(){n = read(); m = read();for(int i=1;i<=n;i++)a[i] = read();for(int i=1;i<=m;i++){int u,v;u = read(); v = read();c1.add(u,v);}for(int i=1;i<=n;i++)if(!dfn[i]) tarjan(i);for(int u=1;u<=n;u++)//缩点 for(int j=c1.head[u];j;j=c1.nxt[j]){int v = c1.ver[j];if(fa[u] == fa[v]) continue;c2.add(fa[u],fa[v]); in[fa[v]]++;}/*...*/return 0;
}

#include
using namespace std;
typedef long long ll;
const int N = 1e6 + 100;
vector G[N];
int father[N],val[N],mark;
bool vis[N];
ll dp[N][2];
void addedge(int from,int to){G[from].push_back(to);          //用邻接表建树father[to] = from;              //父子关系
}
void dfs(int u){                    //和洛谷P1352 几乎一样dp[u][0] = 0;                   //赋初值：不参加dp[u][1] = val[u];              //赋初值：参加vis[u] = true;for(int v : G[u]){              //遍历u的邻居vif(v == mark)  continue;   dfs(v);dp[u][1] += dp[v][0];       //父结点选择，子结点不选dp[u][0] += max(dp[v][0],dp[v][1]);  //父结点不选，子结点可选可不选}
}
int check_c(ll u){                  //在基环树中找环上一个点vis[u] = true;int f = father[u];if(vis[f]) return f;            //第2次访问到，是环上一个点else       check_c(f);          //继续向父结点方向找
}
ll solve(int u){                    //检查一棵基环树ll res = 0;mark = check_c(u);              //mark是基环树的环上一个点 dfs(mark);                      //做一次dfsres = max(res,dp[mark][0]);     //mark不参加mark = father[mark];dfs(mark);                      //mark的父结点不参加，再做一次dfsres = max(res,dp[mark][0]);return res;
}
int main(){int n; scanf("%d",&n);for(int i = 1;i <= n;i++){int d;   scanf("%d%d",&val[i],&d);    addedge(d,i);}ll ans = 0;for(int i = 1;i <= n;i++)if(!vis[i]) ans += solve(i);  //逐个检查每棵基环树printf("%lld\n",ans);return 0;
}

#include 
#include 
#include 
#define MAXN 10//定义最大节点数
using namespace std;
vector  G[MAXN];//用邻接表作为图的存储结构
int color[MAXN];//保存每个节点的颜色
int V,E;
void read(){for(int i = 0;i < E;i ++){int s,t;cin >> s >> t;G[s].push_back(t);G[t].push_back(s);}
}
bool dfs(int v,int c){color[v] = c;//给节点 v 染色为 c//依次对 v 相邻的点进行处理for(int i = 0;i < G[v].size();i ++){//如果相邻的点和自己颜色相同则则无法达成目标if(color[G[v][i]] == c) return false;//如果相邻的点没有染色，且对这个点染不同的颜色后，对之相邻顶点的搜索出现矛盾则无法达成目标if(color[G[v][i]] == 0 && !dfs(G[v][i],-c)) return false;}return true;//如果对所有相邻的点都染色成功则返回 true
}
void solve(){//对邻接表中的顶点依次进行搜索染色for(int i = 0;i < V;i ++){if(color[i] == 0){if(!dfs(i,1)){cout << "NO" << endl;return ;}}}cout << "YES" << endl;
}
int main(void)
{cin >> V >> E;read();solve();return 0;
}

#include
#define ll long long 
using namespace std;
ll read(){ll X = 0 , f = 1;char ch = getchar();while(!isdigit(ch) && ch != '-') ch = getchar();if(ch == '-'){f = -1;ch = getchar();}while(isdigit(ch)){X = (X<<1)+(X<<3)+ch-'0';ch = getchar();}return X*f;
}const int N = 510;
const int M = 5e4+10;
int n,m,e;
int ver[M],nxt[M],head[N],tot;
inline void add(int x,int y){ver[++tot] = y;nxt[tot] = head[x];head[x] = tot;
}
bool vis[N];
int match[N];
bool dfs(int x){for(int i=head[x];i;i=nxt[i]){int y = ver[i];if(vis[y]) continue;vis[y] = true;if(!match[y] || dfs(match[y])){match[y] = x;return true;}}return false;
}int main(){n = read(); m = read(); e = read();for(int i=1;i<=e;i++){int u,v;u = read(); v = read();add(u,v);}int ans = 0;for(int i=1;i<=n;i++){memset(vis,0,sizeof(vis));ans += dfs(i);}cout << ans;return 0;
}

#include
using namespace std;
const int INF = 1e9;
const int N = 250;
#define ll long long
int n, m;
ll graph[N][N], pre[N];                  //graph[][]不仅记录图，还是残留网络
ll flow[N];
ll bfs(int s,int t){                     //一次bfs找一条增广路memset(pre,-1,sizeof pre);flow[s] = INF;  pre[s] = 0;          //初始化起点queue Q;  Q.push(s);            //起点入栈，开始bfswhile(!Q.empty()){int u = Q.front();  Q.pop();if(u==t) break;                  //搜到一个路径，这次bfs结束for(int i=1; i<=n; i++){         //bfs所有的点if(i!=s && graph[u][i]>0 && pre[i]==-1){pre[i] = u;  		     //记录路径Q.push(i);flow[i] = min(flow[u], graph[u][i]); //更新结点流量}}}if(pre[t]==-1) return -1;            //没有找到新的增广路return flow[t];                      //返回这个增广路的流量
}
ll maxflow(int s, int t){ll Maxflow = 0;while(1){ll flow = bfs(s,t);              //执行一次bfs，找到一条路径，返回路径的流量if(flow == -1) break;            //没有找到新的增广路，结束int cur = t;                     //更新路径上的残留网络while(cur!=s){                   //一直沿路径回溯到起点int father = pre[cur];       //pre[]记录路径上的前一个点graph[father][cur] -= flow;  //更新残留网络：正向边减graph[cur][father] += flow;  //更新残留网络：反向边加cur = father;}Maxflow += flow;}return Maxflow;
}
int main(){int s,t; scanf("%d%d%d%d",&n,&m,&s,&t);memset(graph,0,sizeof graph);for(int i=0; iint u,v,w;  scanf("%d%d%d",&u,&v,&w);graph[u][v] += w;                //可能有重边}printf("%ld\n",maxflow(s,t));return 0;
}

#include 
using namespace std;
#define ll long long
const ll INF=1e9;
int n,m,s,t;
const int N=250, M=11000;              //M定义为边的两倍：双向边
int cnt=1,head[N];                     //8-16行：链式前向星。cnt初值不能是0，可以是1、3、5
struct {int to, nex, w;} e[M];
void add(int u,int v,int w) {cnt++;                  //cnt初值是1，cnt++后第一个存储位置是cnt=2，是偶数位置e[cnt].to = v;e[cnt].w = w;e[cnt].nex = head[u];head[u] = cnt;
}
int now[N],dep[N];                     //dep[]记录点所在的层次(深度)
int bfs() {                            //在残留网络中构造分层图for(int i=1;i<=n;i++) dep[i]=INF;dep[s] = 0;                        //从起点s开始分层now[s] = head[s];                  //当前弧优化。now是head的拷贝queueQ;  Q.push(s);while(!Q.empty()) {int u = Q.front();   Q.pop();for(int i=head[u]; i>0;i=e[i].nex) {   //搜点u的所有邻居，邻居是下一层int v = e[i].to;if(e[i].w>0 && dep[v]==INF) {      // e[i].w>0表示还有容量Q.push(v);now[v] = head[v];dep[v] = dep[u]+1;             //分层：u的邻居v是u的下一层if(v==t) return 1;             //搜到了终点，返回1}}}return 0;   //如果通过有剩余容量的边无法到达终点t，即t不在残留网络中，返回0
}
int dfs(int u,ll sum) {                        //sum是这条增广路对最大流的贡献if(u==t) return sum;ll k,flow=0;                               //k是当前最小的剩余容量for(int i=now[u]; i>0 && sum>0; i=e[i].nex) {now[u]=i;                              //当前弧优化int v=e[i].to;if(e[i].w>0 && (dep[v]==dep[u]+1)){   //分层：用dep限制只能访问下一层k = dfs(v,min(sum,(ll)e[i].w));if(k==0) dep[v] = INF;   //剪枝，去掉增广完毕的点。其实把INF写成0也行e[i].w -= k;             //更新残留网络：正向减e[i^1].w += k;           //更新残留网络：反向加。小技巧：奇偶边flow += k;               //flow表示经过该点的所有流量和sum -= k;                //sum表示经过该点的剩余流量}}return flow;
}
int main() {scanf("%d%d%d%d",&n,&m,&s,&t);for(int i=1;i<=m;i++) {int u,v,w;   scanf("%d%d%lld",&u,&v,&w);add(u,v,w);  add(v,u,0);      //双向边，反向边的容量是0}ll ans=0;while(bfs()) ans += dfs(s,INF);   //先后做BFS和DFS。当t不在残留网络中时退出printf("%lld",ans);return 0;
}

#include 
using namespace std;
#define ll long long
const ll INF=1e9;
int n,m,s,t ;
const int N=250, M=11000;              //M定义为边的两倍：双向边
int cnt=1,head[N];                     //链式前向星
struct{int from, to, nex, w;} e[M];
void add(int u, int v, int w){cnt++; e[cnt].from = u;e[cnt].to = v;e[cnt].w = w;e[cnt].nex = head[u];head[u] = cnt;
}
int now[M], pre[M]; //pre[]用于记录路径，pre[i]是路径上点i(的存储位置)的前一个点(的存储位置)
int dep[M], gap[M]; //dep[i]: 点i的高度；gap[i]:高度为i的点的数量
void bfs(){                         //用BFS确定各顶点到汇点的距离memset(gap,0,sizeof(gap));     //初始化间隙数组memset(dep,0,sizeof (dep));    //所有点的高度初始为0dep[t] = 1;                    //汇点t的高度是1，其他点的高度都大于1queue Q;    Q.push(t); while(!Q.empty()){int u = Q.front();    Q.pop();gap[dep[u]]++;             //间隙数组：计算高度为dep[u]的结点个数for(int i=head[u]; i>0; i=e[i].nex){ int v = e[i].to;       //v是u的邻居点if(e[i^1].w && dep[v]==0){   //反向边不用处理；高度不等于0的已经处理过了dep[v] = dep[u]+1; Q.push(v);}}}
}
ll Augment(){               //沿着增广路径更新残留网络ll v = t, flow = INF;while(v != s){         //找这个路径的流量int u = pre[v];     //u是v向源点s方向回退的上一个点，相当于DFS的回溯 if(e[u].w < flow)  flow = e[u].w;      //路径上的最小容量就是这个路径的流量v = e[u].from;      //更新v，继续回退}v = t;while(v != s){         //更新残留网络int u=pre[v];      //向源点s方向回退e[u].w -= flow;    //正向边e[u^1].w += flow;  //反向边。用到了奇偶边的技巧v = e[u].from;     //更新v，继续回退}return flow;           //返回这个路径的流量
}
void ISAP(){     bfs();                //用bfs()求每个点到汇点的距离（高度）ll flow = 0;          //计算最大流 int u = s;	        //从源点s开始找增广路径memcpy(now, head, sizeof (head));  //当前弧优化。now是head的拷贝while(dep[s] <= n){                //最大距离（高度）是n if(u == t){                    //找到了一条增广路径flow += Augment();        //更新残留网络，更新流量u = s;                    //回到s，重新开始找一条增广路径}bool ok = 0;                   //用于判断是否能顺利往下走for(int i=now[u]; i; i=e[i].nex){   //在u的邻居中确定路径的下一个点int v = e[i].to;                //v是u的邻居点if(e[i].w && dep[v]+1==dep[u]){ //沿着高度递减的方向找下一个点ok = 1;              //顺利找到了路径的下一个点pre[v] = i;          //记录路径now[u] = i;          //记录当前弧，下一次跳过它u = v;               //u更新为路径的下一个点vbreak;               //退出for，回到while循环，继续找路径的下一个点}}if(!ok){        //路径走不下去了，需要更新u的高度重新走if(!--gap[dep[u]]) break;  //u的下一个深度的点没有了，断层了，退出whileint mindep = n+10;         //mindep用于计算u的邻居点的最小高度。初值比n大就行for(int i=head[u]; i; i=e[i].nex){   //在u的邻居中找最小的高度int v = e[i].to;if(dep[v]
scanf("%d%d%d%d", &n,&m,&s,&t);
for(int i=1; i<=m; ++i){
int u,v,w;   scanf("%d%d%d",&u,&v,&w);
add(u,v,w);  add(v,u,0);         //反向边的初始容量是0}ISAP();return 0;
}

#include 
#include 
#include 
#include 
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int dis[N], pre[N], preve[N]; //dis[i]记录起点到i的最短距离。pre和 preve见下面注释
int n, m;
struct edge{int to, cost, capacity, rev;        //rev用于记录前驱点edge(int to_,int cost_,int c,int rev_){to=to_; cost=cost_; capacity=c; rev=rev_;}
};
vector e[N];           //e[i]：存第i个结点连接的所有的边
void addedge(int from,int to,int cost,int capacity){//把1个有向边再分为2个e[from].push_back(edge(to, cost, capacity, e[to].size()));e[to].push_back(edge(from, -cost, 0, e[from].size()-1));
}
bool spfa(int s, int t, int cnt){          //套SPFA模板bool inq[N];memset(pre, -1, sizeof(pre));for(int i = 1; i <= cnt; ++i) {dis[i]=INF; inq[i]=false; }dis[s] = 0;queue  Q;Q.push(s);inq[s] = true;while(!Q.empty()){int u = Q.front();Q.pop();inq[u] = false;for(int i=0; i < e[u].size(); i++)if(e[u][i].capacity > 0){int v = e[u][i].to, cost = e[u][i].cost;if(dis[u]+cost < dis[v]){dis[v] = dis[u]+cost;pre[v] = u;        //v的前驱点是upreve[v] = i;      // u的第i个边连接v点if(!inq[v]){inq[v] = true;Q.push(v);}}}}return dis[t] != INF;             //s到t的最短距离（或者最小费用）是dis[t]
}
int mincost(int s,int t,int cnt){     //基本上是套最大流模板int cost = 0;while(spfa(s,t,cnt)){int v = t, flow = INF;        //每次增加的流量while(pre[v] != -1){          //回溯整个路径，计算路径的流int u = pre[v], i = preve[v];         //u是v的前驱点，u的第i个边连接vflow = min(flow, e[u][i].capacity);   //所有边的最小容量就是这条路的流v = u;                                //回溯，直到源点}v = t;while(pre[v] != -1){                      //更新残留网络int u = pre[v], i = preve[v];e[u][i].capacity -= flow;             //正向减e[v][e[u][i].rev].capacity += flow;   //反向加，注意rev的作用v = u;                                //回溯，直到源点}cost += dis[t]*flow;    //费用累加。如果程序需要输出最大流，在这里累加flow}return cost;                //返回总费用
}
int main(){while(~scanf("%d%d", &n, &m)){for(int i=0;iint u,v,w; scanf("%d%d%d",&u,&v,&w);addedge(u,v,w,1); addedge(v,u,w,1);  //把1个无向边分为2个有向边            }int s = n+1, t = n+2;addedge(s,1,0,2);           //添加源点addedge(n,t,0,2);           //添加汇点printf("%d\n", mincost(s,t,n+2));}return 0;
}