網(wǎng)絡(luò)流建模思路

想辦法讓一個流或一組割代表一種方案。

無源匯上下界可行流

先令每條邊的流量為它的下界，此時每個點可能不滿足流量守恒。對每個點求出它的凈流量：即流入減流出。

有源匯上下界可行流

集合劃分模型

假設(shè)有若干個元素，每個元素要么放到A，要么放到B。每個元素放到A/B有相應(yīng)的代價，還有形如“若x在集合A，y在集合B，則有z的代價”的限制。
Sol：
一個元素如果最終和S相連，則相當(dāng)于分到了A集合，如果和T相連則分到B集合。
連邊，跑最小割即可。
注意，如果邊權(quán)存在負(fù)數(shù)，可以令該元素連向A的邊和連向B的邊同時加一個正數(shù)，在最終答案中減去加的這個數(shù)即可。
這樣做的正確性在于該元素連向A的邊和連向B的邊一定割且僅割一條邊，那么不管割哪條邊，對最終的影響是相同的。

最大權(quán)閉合子圖

給定一張有向圖，點有點權(quán)，選一個點集使得這個點集中的任意一條出邊仍然指向這個點集內(nèi)部。要求點權(quán)和的最大值。
實際上，最大權(quán)閉合子圖有一個更加貼合實際建模的定義：有若干個限制，每個限制形如選了\(u\)就必須選\(v\)，選\(u\)有\(a_u\)的價值，求最大價值。
考慮集合劃分模型。不選的話有\(w_u\)的代價，那么從\(S\)向\(u\)連\(w_u\)的邊，從\(u\)向\(T\)連\(0\)邊，對于原圖中的一條邊\((u,v)\),同樣連一條\((u,v)\)的邊，邊權(quán)為\(inf\)。
但是\(w_u\)肯定有負(fù)數(shù)，否則直接選全集就行了，但是網(wǎng)絡(luò)流的容量是不能有負(fù)數(shù)的。我們令邊權(quán)小于\(0\)的點連向\(S\)的邊和連向\(T\)的邊同時加上\(-w_u\)，那么邊權(quán)就都為正了。然后邊權(quán)為\(0\)的邊我們實際上就可以直接忽略了。
最終答案為\(\sum_{w_u>0}w_u-mincut\)

最小路徑點覆蓋

Pro：給定一張DAG，要求用最少路徑（不重復(fù)）覆蓋所有點

Sol：

考慮調(diào)整的方法，初始每個點作為一條單獨的鏈，顯然這是合法的。考慮合并鏈。
把每個點拆成出點和入點，對于原圖中的邊，在拆點二分圖上從出點到入點連邊。那么

解釋：

每條匹配邊相當(dāng)于把兩條鏈連接起來，也就是所選的路徑上的邊。每選一條，答案減一。每個出點只能選一條匹配邊，每個入點也只能選一條匹配邊，這與路徑上的點最多有一個前驅(qū)和后繼相對應(yīng)。
注意，只有DAG能這么做，如果有環(huán)，二分圖也可能出現(xiàn)環(huán)。

ex

如果允許路徑相交，相當(dāng)于可以跳過路徑上的一些點。這時，我們先做一遍傳遞閉包，便可實現(xiàn)“跳過去”這一操作，再做普通的最小路徑點覆蓋即可。

費用流

SSP算法可以求解初始無負(fù)環(huán)情況下的費用流。復(fù)雜度O(nmf),但是出題人一般不會卡這種算法。
可以證明，只要初始無負(fù)環(huán)，那么在增廣過程中，殘量網(wǎng)絡(luò)上一定不會出現(xiàn)負(fù)環(huán)。OIwiki上的證明
但是有可能會出現(xiàn)零環(huán)，因此dinic函數(shù)中要加一個vis標(biāo)記，不重復(fù)訪問節(jié)點。

二分圖最小點覆蓋

對于一般圖顯然有最小點覆蓋大于等于最大匹配，這是因為每個匹配邊都至少需要一個點來覆蓋

而根據(jù)konig定理可以證明二分圖最小點覆蓋等于最大匹配
證明方式考慮從左部的每個非匹配點出發(fā)重新找一次增廣路（一定會失敗），把經(jīng)過的點都進(jìn)行標(biāo)記，最終左部所有的未標(biāo)記點和右部所有的標(biāo)記點即構(gòu)成最小點覆蓋

實際求的過程中用最小割可以很方便的實現(xiàn)（分別枚舉S和T所連的剩余容量為0的邊對應(yīng)的點即為最小點覆蓋）

二分圖最大獨立集

容易發(fā)現(xiàn)最大獨立集和最小點覆蓋是一一對應(yīng)的互補關(guān)系，兩者互為補集，直接取最小點覆蓋剩下的點就是最大獨立集。

差分約束

對若干個變量之間的差分進(jìn)行約束，求出一組解（有環(huán)則無解）
注意，在求最短路時，差分約束會直接求出字典序最大的解，證明考慮最短路樹（每個變量會盡量頂滿上界）
如果要求字典序最小，只需令所有變量取反，然后相應(yīng)的修改限制即可。例如\(x_i<=x_j+dis=>(-x_j)<=(-x_i)+dis\),也就是把連邊的方向取反，最后再反回來即可。
[AGC056C]
很厲害的題。
如果設(shè)vi為每個點的前綴和進(jìn)行差分約束的話，需要用spfa來求最短路，考慮給\(v_i\)換一個意義，設(shè)\(v_i\)表示前綴\(i\)中0的數(shù)量-1的數(shù)量。那么區(qū)間的限制只需在兩端點處連0的邊權(quán)即可。
對于相鄰兩點間的關(guān)系我們先連長度為1的邊。題目讓字典序最小也就是\(v_i\)字典序最大，直接差分約束即可。
那么是否會出現(xiàn)相鄰點的\(v\)相等的情況，感性理解一下在要求字典序最大的情況下，你讓兩個相等一定不優(yōu)。

帶權(quán)并查集

似乎可以做csp2022t4？復(fù)雜度很優(yōu)秀？

dfs樹

CF118E

P4151

tarjan

CF160D
給定一張無向圖，輸出哪些邊可以在最小生成樹中，哪些邊一定在最小生成樹中，哪些邊一定不在最小生成樹中。
先求出一顆最小生成樹，考慮每條邊能否被替換？

圓方樹

對于一個無向圖，給他的每個點雙（一條邊也視為一個點雙）都定義一個方點。其他點都是圓點
方點向它對應(yīng)的點雙中的每個圓點連邊，形成一顆樹，即為圓方樹。
性質(zhì)：圓點只和方點連邊，方點只和圓點連邊
構(gòu)建：類似于求割點，每次要從棧中彈出一個點雙時，建一個方點與這些點連邊
說到簡單路徑，就必須提一個關(guān)于點雙很好的性質(zhì)：對于一個點雙中的兩點，它們之間簡單路徑的并集，恰好完全等于這個點雙。
即同一個點雙中的兩不同點 u,v 之間一定存在一條簡單路徑經(jīng)過給定的在同一個點雙內(nèi)的另一點 w。
證明考慮

只有紅黑有交、紅紫有交、綠黑有交、綠紫有交的情況可能找不到x-y-z的路徑
然后以綠黑有交為例，必然是走完黑之后，綠的一段前綴是黑的一段后綴，否則一定可以調(diào)整成這樣
又因為綠紫有交，所以綠的一段前綴是紫的一段后綴
所以紫、黑就出現(xiàn)公共后綴了，但是紫黑是不交的
于是就出現(xiàn)了矛盾。也就是說如果綠黑有交，令綠和黑擁有一段共同后綴，那么綠和紫一定沒有交，所以結(jié)論成立。
由此可以推出：原圖中兩個點的所有簡單路徑的并即為兩點在圓方樹路徑上所有方點所代表的點雙的并。
鐵人兩項代碼，注意其中圓方樹的構(gòu)建部分，

namespace Tj
{
	int dfn[N],low[N],tot,stk[N],top,num,siz[N],w[N],s[N],fa[N];
	vector<int>v[N];
	int ans;
	void tarjan(int x)
	{
		dfn[x]=low[x]=++tot;
		stk[++top]=x;
		for(int i=hd[x];i;i=e[i].nxt)
		{
			int y=e[i].to;
			if(dfn[y]) low[x]=min(low[x],dfn[y]);
			else
			{
			   tarjan(y);
			   low[x]=min(low[x],low[y]);
			   if(low[y]>=dfn[x])
			   {
					++num;int z;
					do
					{
						z=stk[top--];
						v[z].pb(num);v[num].pb(z);
						w[num]++;
					}while(z!=y);
					w[num]++;v[x].pb(num);v[num].pb(x);		   	
			   }
			}
		}

	}
	void dfs(int x,int sum,int num)
	{
		sum+=w[x];
		if(x<=n) ans+=(num-1)*sum,siz[x]=1;
		int tmp=0;
		for(int i=0;i<v[x].size();++i)
		{
			int y=v[x][i];
			if(y==fa[x]) continue;
			fa[y]=x;dfs(y,sum,num);siz[x]+=siz[y];
			s[x]+=siz[y]*(siz[y]-1)/2;tmp+=s[y];
		}
		s[x]=siz[x]*(siz[x]-1)/2-s[x];
		ans-=sum*s[x];
		ans-=tmp*sum;
	}
	void work()
	{
		num=n;for(int i=1;i<=n;++i) w[i]=-1;
		for(int i=1;i<=n;++i) 
		  if(!dfn[i]) 
		  {
		  	int tt=tot;
			tarjan(i);
			top--;
			dfs(i,0,tot-tt);
		  }
		cout<<ans*2;
	}
}

2-SAT

問題：

給定n個bool 變量，和若干個限制，每個限制都只牽涉兩個變量，即為2-SAT，若一個限制同時牽涉多個變量，即為k-SAT，是NPC問題。

Sol：

類似擴展域并查集，把每個變量拆成\(x\)和\(x'\),把限制轉(zhuǎn)化成\(x\Rightarrow y\)的形式,并形象地從\(x\)到\(y\)連一條有向邊。注意逆否命題也要連邊，因此如果忽略邊的方向，2-SAT的連邊是對稱的。
將所有限制轉(zhuǎn)化完后，對得到的有向圖進(jìn)行強聯(lián)通縮點，注意到一個強連通分量中的命題要么全都為真，要么全都為假。
定理：當(dāng)且僅當(dāng)存在一個變量\(x\)和\(x'\)在同一個強連通分量中時，2-SAT問題無解
首先，充分性是顯然的，\(x\)和\(x'\)不可能同時為真或假
否則，一定能構(gòu)造出一組解。

構(gòu)造解：

縮點后的圖形成一個DAG，由于2-SAT問題連邊的對稱性，如果\(x\)和\(y\)在同一個SCC中，那么\(\lnot x\)和\(\lnot y\)也必定在同一個強連通分量中，因此縮點之后的DAG上的每個點也都有唯一對應(yīng)的一個點，擁有恰好大小相等，所含的變量完全相反的點。
具體的構(gòu)造方法如下：
按拓?fù)湫驈拇蟮叫?/strong>，檢查這個點是否被標(biāo)記過，若沒有，則令這個點為真，同時標(biāo)記這個點對應(yīng)的點為假。
若已被標(biāo)記過為假，則檢查下一個點。

for(int i=1;i<=n;++i)
val[i]=c[i]<c[i+n];