题目传送门：https://www.codechef.com/problems/PARADE
神犇题解：http://blog.csdn.net/jasonvictoryan/article/details/53395098
这题先只考虑一个询问的情况
这显然可以使用拆点+二分图最大权匹配去做
具体来说：每个点拆成出度和入度两个点，然后出度放左边，入度放右边
考虑每找到一条增广路，就是在原图中走了一条边
那么不管是连接了两条路径，或是新走到一个点，都会使总费用减少一个$C$
但每走一次增广路，都会花费一些费用$v$
显然我们应该在$v > C$的时候停止增广
现在考虑多个询问
因为是费用流算法，所以单次增广的费用$v_i$是单调不减的
于是我们可以记录每一次增广的$v_i$。对于询问就二分，然后求前缀和就好
当然不想二分，也可以先排个序然后扫一遍，反正总的时间复杂度主要还是卡在费用流那里
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4773
神犇题解：http://www.cnblogs.com/lytccc/p/6616625.html
我们可以使用倍增Floyd来解决这个问题
具体来讲：
我们从大到小维护走$2^k$步后的最短路
如果出现负环，那么不继承，舍弃掉更改
如果没有出现负环，那么更新数组
时间复杂度：$O(n^3 \log n)$
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2521
神犇题解：http://krydom.com/bzoj2521/
这题有一个非常显然的贪心：做Kruskal的时候，如果会使那条边的两个端点连在一起就暴力加权值
但这样显然也是错误的，因为我们可能是在之前的步骤就废掉一些边
于是怎么解决这个问题呢？
我们相当于不能在某两个端点之间有通路，那么这和网络流的增广路相同
于是我们把边的容量设为暴力改的时候需要的花费，然后跑一遍最小割就可以了
给定一个$n(n \le 100)$个点的连通图
不同顶点之间有$n^2$个最小割
现在给定这$n^2$个最小割，让你构造一个图使其满足条件
据说这是论文题？
因为任意两点间的最小割可以用最小割树来表示
所以我们考虑构造一个树形结构
因为一条路径上的最小割相当于取$min$，所以流量大的不会影响流量小的
所以我们先按边权从大到小排序
如果当前这条边的两个端点已经在一个连通块内，那么暴力判断是否符合要求
如果不在一个块内，那么连一条边
至于为什么这样是对的，因为已经按权值排序了
如果不在一个连通块内，还不连边，那么最终连通这两块的权值一定大于要求的最小割，所以必须立刻连边
至于已经连边了还冲突的话，因为之前的边都是必要的，所以也没有调整的需要，一定是无解的
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 109;
const int M = N * N << 1;
const int INF = 1e9;
int n,tot,head[N],nxt[M],to[M],cost[M],fa[N];
struct Data{
int u,v,val;
inline Data() {}
inline Data(int a, int b, int c):u(a),v(b),val(c) {}
inline bool operator < (const Data &B) const {
return val > B.val;
}
}p[N*N*N];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void AddEdge(int u, int v, int c) {
static int E = 1; cost[E+1] = cost[E+2] = c;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}
int cal(int w, int f, int pur, int mn) {
if (w == pur) return mn;
for (int i=head[w],tmp;i;i=nxt[i]) {
if (to[i] != f) {
tmp = cal(to[i], w, pur, min(mn, cost[i]));
if (~tmp) return tmp;
}
} return -1;
}
int find(int x) {return x==fa[x]? x: fa[x]=find(fa[x]);}
int main() {
n = read();
for (int i=1,v;i<=n;i++) {
fa[i] = i;
for (int j=1;j<=n;j++) {
if (v=read(), i==j) continue;
p[++tot] = Data(i, j, v);
}
}
sort(p+1, p+1+tot);
for (int i=1;i<=tot;i++) {
int u=p[i].u, v=p[i].v, val=p[i].val;
if (find(u) == find(v)) {if(cal(u,u,v,INF)!=val)cout<<-1,exit(0);}
else fa[find(u)] = fa[v], AddEdge(u, v, val);
}
cout<<n-1<<endl;
for (int i=2;to[i];i+=2) printf("%d %d %d\n",to[i],to[i+1],cost[i]);
return 0;
}
给定$n(n \le 300)$个外星人，给定$m(m \le 1500)$个地球人，再给定任意地球人与外星人的关系
关系由一个$nm$的0/1矩阵给出，表示第$i$个外星人是否能与第$j$个地球人配对
要求每个外星人至少与一个地球人配对，地球人只能与至多一个外星人匹配
问由哪些关系一定不可能出现在合法的匹配方案中
这是一道基础图论题
我们可以先来考虑一个简单的版本：地球人个数与外星人一样
那么我们可以先用二分图匹配跑一个完备匹配出来
此时在匹配中的边一定可以出现在合法的匹配方案中
只考虑不在当前匹配中的边，那么一定是走一条像增广路一样的东西
就是一条匹配边，一条非匹配边交叉着走。最后走一个偶环绕回来
于是我们对于从左边连到右边的边，只保留非匹配边
对于从右到左的边，我们只保留匹配边。这样就可以保证是偶环了
至于能不能走回来，我们发现这就是一个有向图的强连通分量
于是我们再跑一个Tarjan，判断一下就可以了
现在考虑地球人与外星人不等的情况
我们可以把外星人补到与地球人一样多啊！
就是加一些可以与所有地球人匹配的外星人就可以了
当然不加点，大力讨论一波也是可以的
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 3009;
const int M = N * N << 1;
const int INF = 1e9;
int head[N],nxt[M],to[M],flow[M],low[N],dfs[N];
int n,m,S,T,E=1,mth[N],id[N][N],num[N],ins[N]; char pat[N];
stack<int> stk;
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline int AddEdge(int u, int v, int f=0) {
if (f) {
to[++E] = v; nxt[E] = head[u]; head[u] = E;
to[++E] = u, nxt[E] = head[v], head[v] = E;
flow[E - 1] = f; return E - 1;
} else to[++E] = v, nxt[E] = head[u], head[u] = E;
}
class Network_Flow{
int dis[N],cur[N]; queue<int> que;
public:
inline int MaxFlow() {
int ret = 0;
while (BFS()) {
memcpy(cur,head,sizeof(cur));
ret += DFS(S, INF);
} return ret;
}
private:
int DFS(int w, int f) {
if (w == T) return f; int ret = 0;
for (int &i=cur[w],tmp;i;i=nxt[i]) {
if (flow[i] && dis[to[i]] == dis[w] + 1) {
tmp = DFS(to[i], min(f, flow[i]));
flow[i] -= tmp; flow[i^1] += tmp;
f -= tmp; ret += tmp;
if (!f) return ret;
}
} return ret;
}
inline bool BFS() {
memset(dis,60,sizeof(dis));
dis[S] = 0; que.push(S);
while (!que.empty()) {
int w = que.front(); que.pop();
for (int i=head[w];i;i=nxt[i]) {
if (flow[i] && dis[to[i]] > INF) {
dis[to[i]] = dis[w] + 1;
que.push(to[i]);
}
}
} return dis[T] < INF;
}
}Dinic;
void Tarjan(int w) {
static int dfs_cnt = 0, scc_cnt = 0;
dfs[w] = low[w] = ++dfs_cnt; stk.push(w); ins[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (!dfs[to[i]]) Tarjan(to[i]), low[w] = min(low[w], low[to[i]]);
else if (ins[to[i]]) low[w] = min(low[w], dfs[to[i]]);
}
if (low[w] == dfs[w]) {
for (scc_cnt++;!stk.empty();stk.pop()) {
num[stk.top()] = scc_cnt; ins[stk.top()] = 0;
if (stk.top() == w) {stk.pop(); break;}
}
}
}
int main() {
n = read(); m = read(); S = 0; T = N - 1;
memset(id, -1, sizeof(id));
for (int i=1;i<=n;i++) {
scanf("%s",pat+1);
for (int j=1;j<=m;j++) {
if (pat[j] == '1') {
id[i][j] = AddEdge(i, m + j, 1);
}
}
}
for (int i=1;i<=n;i++) AddEdge(S, i, 1);
for (int i=1;i<=m;i++) AddEdge(m + i, T, 1);
if (Dinic.MaxFlow() != n) {
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) putchar('1');
puts("");
}
} else {
E = 1; memset(head,0,sizeof(head));
for (int i=1;i<=n;i++) for (int j=1;j<=m;j++)
if (~id[i][j] && !flow[id[i][j]]) {mth[j] = i; break;}
for (int i=n+1,j=1;i<=m;i++,j++) {while(mth[j])j++;mth[j]=i;}
for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) if (~id[i][j] || i > n) {
if (mth[j] == i) AddEdge(m+j, i); else AddEdge(i, m+j);}
for (int i=1;i<=m*2;i++) if (!dfs[i]) Tarjan(i);
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((~id[i][j]) && (mth[j] == i || num[i] == num[m+j])) putchar('0');
else putchar('1');
} putchar('\n');
}
}
return 0;
}
Mr. Panda很喜欢玩游戏。最近，他沉迷在一款叫Tube Master的游戏中。
在Tube Master游戏中，玩家可以在$N\times M (N,M \le 30)$的网格中放置管道。每个网格要么为空格子，要么放置下面四种管子中的一种。
当两个相邻（有公共边的格子视为相邻）的格子中间有管道连接（例如下面这幅图），那么玩家将会得到一些分数（具体细节将在输入描述中给出）。
游戏中，有些格子是关键格子。对于每一个关键格子，玩家必须放置这四种管道中的任意一种，不得留空，否则玩家将输掉整局游戏。
玩家放好管道后，这个$N\times M$的网格必须满足以下两个条件，否则玩家将输掉整局游戏。
1. 每个格子要么没有管道，要么这个格子的管道是环形管道的一部分。
2. 每个关键格子必须放置管道。
特别地，如果没有关键格子，那么空网格也是一组合法解。
可以有多个环。
在上面三张图中，灰色格子是关键格子。其中：
左边的图不合法，因为关键格子没有放管道。
中间的图合法。
右边的图不合法，因为管道没有构成环。
Mr. Panda想要打赢这局游戏并且拿到尽可能多的分数。你能帮他计算他最多能拿多少分吗？
这是一道非常玄妙的费用流题目
我们先将所有的点黑白染色
然后我们钦定黑点是从横变竖，白点是从竖变横（如果刚好相反的话，我们把这个环给反向就可以了）
之后我们再把每个点拆成入度和出度两个点，入度全部放左边，出度放右边
根据我们的旨意，黑色的入度只能匹配其上下的方格的出度，其出度只能匹配其左右两个方格的入度
我们在连边的时候，注意这个限制。
根据这个题目的启示TopCoder – Curvy on Rails，如果存在完备匹配，这个匹配的意义一定是几个圈
现在唯一的问题就是，有一些点可以不选了
那么我们可以认为他的出度与自己的入度匹配了（自环）
于是对于不必选的点我们连一条自己到自己的边，必选的边不连
之后搞一发费用流就可以了！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5000;
const int M = 100000;
const int INF = 1e9;
int n,m,S,T,E,head[N],nxt[M],cost[M],flow[M],to[M];
int pos[30][30],cx[30][30],cy[30][30],vis[30][30];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int AddEdge(int u, int v, int c, int f) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
return E - 1;
}
class Minimum_Cost_Flow{
int dis[N],sur[N],inq[N];
queue<int> que;
public:
inline int MaxFlow() {
int ret_cost = 0, ret_flow = 0;
for (int f=INF,w;SPFA();f=INF) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret_cost += dis[T] * f;
ret_flow += f;
}
return ret_flow == n * m? ret_cost: -INF;
}
private:
bool SPFA() {
memset(dis,60,sizeof(dis));
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;
inline int id(int x, int y, int t) {
return ((y - 1) * n + x - 1) * 2 + t;
}
int main() {
for (int TT=read(),t=1;t<=TT;t++) {
S = 0; T = N - 1; E = 1; memset(head,0,sizeof(head));
printf("Case #%d: ",t); m = read(); n = read();
for (int j=1,v;j<=m;j++) for (int i=1;i<n;i++) cx[i][j] = -read();
for (int j=1,v;j<m;j++) for (int i=1;i<=n;i++) cy[i][j] = -read();
for (int e=read(),x,y;e;e--) x=read(), y=read(), vis[y][x] = t;
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
AddEdge(S, id(i,j,1), 0, 1);
AddEdge(id(i,j,2), T, 0, 1);
if (vis[i][j] != t) AddEdge(id(i,j,1), id(i,j,2), 0, 1);
}
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=m;j++) {
if ((i + j) & 1) {
if (i < n) AddEdge(id(i+1,j,1), id(i,j,2), cx[i][j], 1);
if (i > 1) AddEdge(id(i-1,j,1), id(i,j,2), cx[i-1][j], 1);
if (j < m) AddEdge(id(i,j,1), id(i,j+1,2), cy[i][j], 1);
if (j > 1) AddEdge(id(i,j,1), id(i,j-1,2), cy[i][j-1], 1);
}
}
}
int tmp = MCMF.MaxFlow();
if (tmp == -INF) puts("Impossible");
else printf("%d\n",-tmp);
}
return 0;
}
—————————— UPD 2017.3.22 ——————————
Claris给我讲了一点新的姿势，不需要原来的无源汇带上下界费用流了
只需要一个普通的费用流即可，已经更新
Claris真是太强了 _(:з」∠)_
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3638
神犇题解Ⅰ：http://blog.csdn.net/werkeytom_ftd/article/details/50950623
神犇题解Ⅱ：http://hzwer.com/6715.html
这题非常的妙啊！
但我还是点亮手动增广这个技能点 QwQ
考虑单次询问整个区间，我们建一个费用流的图就可以辣！
然后我们发现这个费用流的每次增广相当于区间取反+区间询问最大连续字段和
这个是线段树的经典问题，于是我们用线段树来模拟增广的过程就可以辣！
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3919
神犇题解：http://www.cnblogs.com/clrs97/p/4668647.html
我们自己想一想，这货如果没有Po那就是一个BFS
现在考虑Po的作用，那一定是发射一个Po之后，正常移动是为了走到最近的墙来使用Po
于是我们先预处理出每一个点上下左右每一个方向遇到的第一堵墙
再求出这到这四个点的最近距离$l$
那么如果我们当前在$i$号点，那么我们可以花费$1$的代价走到相邻的四个点
也可以花$l+1$的代价走到上下左右第一个遇到障碍的点
这显然是一个最短路问题，跑一个Dijksta就可以啦！
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3482
神犇题解：http://www.cnblogs.com/clrs97/p/4675155.html
我们发现一条路径的长度为$ax+b$，是一条直线的形式
那么我们如果求出所有直线的凸包，那么就可以$O(n)$计算答案了
现在考虑如何搞出凸包：
若两条直线的斜率相等，那么纵截距较小的一定优于纵截距较大的
于是我们可以定义状态$f_{i,j}$表示到达$i$点，斜率为$j$，的路径纵截距最小是多少
这个我们可以使用Dijkstra搞出来，之后我们显然可以$O(n)$构造出凸包了
有了凸包后，每一条线段的贡献就是一个等差数列，这个显然可以$O(1)$计算
于是总的时间复杂度就是$O(Qn^2 \log (n^2))$
给定一棵$n(n \le 10^5)$个节点的以$1$为根的有根树，第$i$个结点上有$c_i$个食物，其父亲为$\lfloor \frac{i}{2} \rfloor$
现在依次给出$m$个拉姆，依次询问前$i$个拉姆都有东西吃的最短移动距离和
依次输出这$m$次询问的答案
如果点数很小的话，我们显然可以跑个费用流就可以了！
但这题点这么多怎么办 QwQ
那我们就手动增广！
考虑维护一个$val_i$表示以$i$为根的子树中最近的有食物的点到$i$的距离
于是我们可以花$O(\log n)$的时间暴力在树上爬一爬就可以代替费用流的SPFA
然后考虑修改沿途边的边权，因为树高是$\log n$级别的，于是我们也是暴力修改就好
最后再用更新一下受影响的$val_i$来方便下次增广就可以辣！
以前听说过手动增广的题目，不过一次都还没有写过
这次写一写感觉这货非常好玩啊！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 100009;
const int INF = 1e9;
int n,m,vout,cnt[N],pos[N];
int sur[N],val[N],cost[N];
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}
inline int LCA(int u, int v) {
for (;u!=v;u>>=1)
if (u < v) swap(u, v);
return u;
}
inline void update(int w) {
static int ls, rs, cl, cr;
if (cnt[w]) sur[w] = w, val[w] = 0;
else sur[w] = 0, val[w] = INF;
if ((ls=w<<1) <= n) {
cl = cost[ls] > 0? -1: 1;
if(val[ls] + cl < val[w]) {
val[w] = val[ls] + cl;
sur[w] = sur[ls];
}
}
if ((rs=ls|1) <= n) {
int cr = cost[rs] > 0? -1: 1;
if(val[rs] + cr < val[w]) {
val[w] = val[rs] + cr;
sur[w] = sur[rs];
}
}
}
inline void modify(int w, int p, int delta) {
while (w != p) {
cost[w] += delta;
update(w); w >>= 1;
}
}
inline int query(int w, int &ans) {
static int ret, delta; delta = 0;
for (;w;w>>=1) {
if (val[w] + delta < ans) {
ans = val[w] + delta;
ret = sur[w];
}
delta += cost[w] >= 0? 1: -1;
} return ret;
}
int main() {
n = read(); m = read();
for (int i=1;i<=n;i++) cnt[i] = read();
for (int i=1;i<=m;i++) pos[i] = read();
for (int i=n;i;i--) update(i);
for (int i=1,u,v,ans=INF;i<=m;++i,ans=INF) {
cnt[v=query(u=pos[i], ans)]--;
printf("%d\n",vout+=ans);
int lca = LCA(u, v);
modify(u, lca, 1); modify(v, lca, -1);
for (;lca;lca>>=1) update(lca);
}
return 0;
}
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2437
神犇题解：http://blog.csdn.net/qpswwww/article/details/45368587
我们先将整个棋盘黑白染色，将空格棋子所在方格的颜色分类
在可相互转化的状态之间连边，那么这就是一张二分图了
那么原题的问题转换为：
给定一张二分图，每次沿边移动一次
每个点只能到达一次，最后谁不能动谁就输了
询问每一个点作为起点时是否先手必胜
考虑一个点如果在任意一种最大匹配当中，那么先手每一次走匹配边，则后手必败
换一句话来说，如果一个点一定在最大匹配当中，那么这个点是先手必胜的
再考虑一下，如果一个点不一定在最大匹配当中，那么删掉这个点之后存在最大匹配，那后手走到那个点去就可以了！
再换一句话来说，如果一个点不一定在最大匹配中，那么这个点先手必败
现在我们只需要求出一个点是否在最大匹配中就可以了！
我们可以枚举这个点，将其删掉后跑最大匹配验证，但复杂度是$O(n^4)$的
或者我们可以用今年冬令营的那个一般图匹配的算法来做，时间复杂度是$O(n^3)$的
不过我们可以又一个常数更小的算法
我们可以先求出一个最大匹配，然后假设当点在点$a$
将其删掉后，看$a$的匹配点$b$还能不能匹配即可
博弈题居然还能这么玩！
真的是长见识了 _(:з」∠)_
不过代码好难写啊，不想写代码 ┑(￣Д ￣)┍
题目传送门：http://codeforces.com/contest/782/problem/D
为什么题面这么难懂啊？！
感觉出题人的英文比我好不到哪里去啊？！
差一点写成二分图了，还好室友嘈代码难写的时候多问了一句 _(:з」∠)_
我们发现每个人只有两个状态
于是我们撸一发2-SAT就可以A辣！
2-SAT判定有没有解是可以做到$O(m)$的，写个强连通就可以了
不过我这份代码是$O(m^2)$的啊！
为什么不会T？我的$m$是$O(n^2)$的啊
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 5000;
const int M = 5000009;
int n,que[N],cnt,head[N],to[M],nxt[M],mark[N];
char pat[2][100];
struct Data{
char p[4];
inline bool operator < (const Data &B) const {
for (int i=0;i<3;i++) {
if (p[i] < B.p[i]) return 1;
else if (p[i] > B.p[i]) return 0;
} return 0;
}
inline bool operator == (const Data &B) const {
return !(*this < B) && !(B < *this);
}
}c1[N],c2[N];
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Add_Edge(int u, int v) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E;
}
inline int id(int w, int t) {
return (w-1)*2 + t + 1;
}
bool DFS(int w) {
if (mark[w]) return true;
if (mark[w^1]) return false;
mark[w] = 1; que[++cnt] = w;
for (int i=head[w];i;i=nxt[i])
if (!DFS(to[i])) return false;
return true;
}
inline bool judge(){
for (int i=2,lim=id(n,2);i<=lim;i+=2) if (!mark[i] && !mark[i+1]) {
cnt = 0; if (DFS(i)) continue;
for (int j=1;j<=cnt;j++) mark[que[j]] = 0;
cnt = 0; if (!DFS(i+1)) return false;
}
return true;
}
int main() {
n = read();
for (int i=1;i<=n;i++) {
scanf("%s%s",pat[0],pat[1]);
Data a; a.p[3] = 0; a.p[0] = pat[0][0]; a.p[1] = pat[0][1]; a.p[2] = pat[0][2];
Data b; b.p[3] = 0; b.p[0] = pat[0][0]; b.p[1] = pat[0][1]; b.p[2] = pat[1][0];
c1[i] = a; c2[i] = b;
}
for (int i=1;i<=n;i++) {
for (int j=1;j<=n;j++) {
if (i == j) continue;
if (c1[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
if (c1[i] == c1[j]) Add_Edge(id(i, 1), id(j, 2));
if (c1[i] == c2[j]) Add_Edge(id(i, 1), id(j, 1));
if (c2[i] == c1[j]) Add_Edge(id(i, 2), id(j, 2));
if (c2[i] == c2[j]) Add_Edge(id(i, 2), id(j, 1));
}
}
if (!judge()) puts("NO");
else {
puts("YES");
for (int i=1;i<=n;i++) {
if (mark[id(i, 1)]) printf("%s\n",c1[i].p);
else printf("%s\n",c2[i].p);
}
}
return 0;
}
—————————— UPD 2017.3.27 ——————————
今天才知道输出一组可行解也是可以$O(m)$的
大概就是搞一发Tarjan，然后在拓扑图上按拓扑逆序染色
题目传送门：https://contest.yandex.ru/neerc2016/contest/3529/problems/D/
敦敦敦题解：http://oi.cyo.ng/wp-content/uploads/2017/03/delight_for_a_cat_solution.pdf
有$n$天，每天只能睡觉或者吃饭，每天睡觉和吃饭的收益不同
要求连续$k$天中，至少有$ms$天睡觉，$me$天吃饭
求最大收益
这题之前在绍一集训的时候考过
但当时并没有改题 QwQ
话说根据方程建费用流这个技能始终没在科技树上点亮啊
正解的话，其实也不难，就是瞎推一推式子
然后可以得到一个和志愿者招募那个题差不多的式子
于是我们撸一发费用流就可以啦！
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N = 1009;
const int M = 5000;
const LL INF = 1e18;
int head[N],to[M],nxt[M],cost[M],flow[M];
int n,k,me,ms,S,T,s[N],e[N],edge[N];
LL vout,dis[N];
inline int Add_Edge(int u, int v, int f, int c) {
static int E = 1;
to[++E] = v; nxt[E] = head[u]; head[u] = E; flow[E] = f; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; flow[E] = 0; cost[E] = -c;
return E - 1;
}
inline int read() {
char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
class Minimum_Cost_Flow{
int sur[N],inq[N];
queue<int> que;
public:
inline LL MaxFlow() {
LL ret_cost = 0;
for (int f=1e9,w;SPFA();f=1e9) {
for (w=T;w!=S;w=to[sur[w]^1]) f = min(f, flow[sur[w]]);
for (w=T;w!=S;w=to[sur[w]^1]) flow[sur[w]] -= f, flow[sur[w]^1] += f;
ret_cost += dis[T] * f;
}
return ret_cost;
}
private:
bool SPFA() {
fill(dis, dis+N, INF);
que.push(S); dis[S] = 0;
while (!que.empty()) {
int w = que.front(); que.pop(); inq[w] = 0;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i] && flow[i]) {
dis[to[i]] = dis[w] + cost[i];
sur[to[i]] = i;
if (!inq[to[i]]) inq[to[i]] = 1, que.push(to[i]);
}
}
}
return dis[T] < INF;
}
}MCMF;
int main() {
S = 0; T = N - 1;
n = read(); k = read();
ms = read(); me = read();
for (int i=1;i<=n;i++) vout += (s[i] = read());
for (int i=1;i<=n;i++) e[i] = read();
Add_Edge(S, n-k+2, k-ms, 0);
Add_Edge(1, T, k-ms, 0);
for (int i=2;i<=n-k+2;i++) Add_Edge(i, i-1, k-ms-me, 0);
for (int i=1;i<=n;i++) edge[i] = Add_Edge(min(i+1, n-k+2), max(1, i-k+1), 1, s[i] - e[i]);
printf("%lld\n",vout-MCMF.MaxFlow());
for (int i=1;i<=n;i++) putchar(flow[edge[i]]? 'S': 'E');
return 0;
}
题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4356
神犇题解Ⅰ：http://www.cnblogs.com/clrs97/p/5196611.html
神犇题解Ⅱ：http://www.cnblogs.com/New-Godess/p/4424149.html
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int L = 400 + 9;
const int N = L * L * 4;
const int M = N * 4;
const LL INF = 1e17;
int n,m,tot,E,head[N],nxt[M],to[M],cost[M];
int cx[L][L],cy[L][L],intree[L][L];
int dx[]={0,1,0,-1,0},dy[]={0,0,1,0,-1};
bool del[L][L][4],vis[L][L],done[N],bst[L][L][4];
LL dis[N];
priority_queue<pair<LL, int> > que;
inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}
inline void Add_Edge(int u, int v, int c) {
to[++E] = v; nxt[E] = head[u]; head[u] = E; cost[E] = c;
to[++E] = u; nxt[E] = head[v]; head[v] = E; cost[E] = c;
}
inline int id(int x, int y, int t = 0) {
if (!t) return x + (y - 1) * (n + 1);
else return (x - 1 + (y - 1) * (n + 1) << 2) + t;
}
inline void Dijkstra(int s) {
memset(done, 0, sizeof(done));
fill(dis, dis+N, INF); dis[s] = 0;
que.push(make_pair(0, s));
for (int w;!que.empty();) {
w = que.top().second; que.pop();
if (done[w]) continue;
done[w] = 1;
for (int i=head[w];i;i=nxt[i]) {
if (dis[to[i]] > dis[w] + cost[i]) {
dis[to[i]] = dis[w] + cost[i];
que.push(make_pair(-dis[to[i]], to[i]));
}
}
}
}
bool mark(int x, int y, int f) {
if (intree[x][y]) return ~intree[x][y]?1:0;
bool tag = vis[x][y];
for (int w=id(x,y),i=head[w];i;i=nxt[i]) {
if (dis[w] + cost[i] == dis[to[i]] && to[i] != f) {
for (int j=1,nx,ny;j<=4;j++) {
nx = x + dx[j]; ny = y + dy[j];
if (id(nx, ny) == to[i]) {
if (mark(nx, ny, w)) {
bst[x][y][j] = tag = 1;
bst[nx][ny][j+2>4?j-2:j+2] = 1;
}
break;
}
}
}
}
intree[x][y] = tag?1:-1;
return tag;
}
int main() {
m = read(); n = read();
del[1][1][2] = del[1][1][4] = 1;
for (int j=1;j<=m;j++) {
for (int i=1;i<=n;i++) {
if (read()) {
vis[i][j] = 1;
del[i][j][4] = 1;
del[i+1][j][3] = 1;
del[i][j+1][1] = 1;
del[i+1][j+1][2] = 1;
}
}
}
for (int j=1,tmp;j<=m;j++) {
for (int i=1;i<=n+1;i++) {
cy[i][j] = tmp = read();
Add_Edge(id(i, j), id(i, j+1), tmp);
}
}
for (int j=1,tmp;j<=m+1;j++) {
for (int i=1;i<=n;i++) {
cx[i][j] = tmp = read();
Add_Edge(id(i, j), id(i+1, j), tmp);
}
}
Dijkstra(id(1,1));
mark(1, 1, id(1, 1));
E = 0; memset(head,0,sizeof(head));
for (int j=1;j<=m+1;j++) {
for (int i=1;i<=n+1;i++) {
if (!del[i][j][1]) {
if (!del[i][j][4] && !bst[i][j][1]) Add_Edge(id(i, j, 1), id(i, j, 4), 0);
if (i <= n && !del[i+1][j][2]) Add_Edge(id(i, j, 1), id(i+1, j, 2), cx[i][j]);
}
if (!del[i][j][2]) {
if (!del[i][j][1] && !bst[i][j][4]) Add_Edge(id(i, j, 2), id(i, j, 1), 0);
if (!del[i][j][3] && !bst[i][j][3]) Add_Edge(id(i, j, 2), id(i, j, 3), 0);
}
if (!del[i][j][3]) {
if (!del[i][j][4] && !bst[i][j][2]) Add_Edge(id(i, j, 3), id(i, j, 4), 0);
if (j <= m && !del[i][j+1][2]) Add_Edge(id(i, j, 3), id(i, j+1, 2), cy[i][j]);
}
if (!del[i][j][4]) {
if (i <= n && !del[i+1][j][3]) Add_Edge(id(i, j, 4), id(i+1, j, 3), cx[i][j]);
if (j <= m && !del[i][j+1][1]) Add_Edge(id(i, j, 4), id(i, j+1, 1), cy[i][j]);
}
}
}
Dijkstra(id(1,1,3));
printf("%lld\n",dis[id(1,1,1)]);
return 0;
}