學完了ISAP，感覺心情舒暢，畢竟ISAP比Dinic好一點。 說到底ISAP其實是Dinic（不熟悉Dinic的人去我的博客找猴子課堂 最大流與最小割（看看思想）,已經置頂）優化版，熟悉的人知道Dinic是通過不斷分層來做的，但是，我們如果用打標記（貂蟬的標記）的方法就會快一些！ 會快的原因就是因 ...
學完了ISAP，感覺心情舒暢，畢竟ISAP比Dinic好一點。
說到底ISAP其實是Dinic（不熟悉Dinic的人去我的博客找猴子課堂----最大流與最小割（看看思想）,已經置頂）優化版，熟悉的人知道Dinic是通過不斷分層來做的，但是，我們如果用打標記（貂蟬的標記）的方法就會快一些！
會快的原因就是因為他省了很多分層的時間，使得他比Dinic要快不少,首先，我們先初始化一遍（從t開始搜，建個分層圖（不是說不用寬搜了嗎）），雖然過程中不用多次分層，但初始化分層，使得代碼要乾的事情少了不少（因為讓代碼通過自身調整標記要O(n^2)時間，但如果用寬搜初始化分層就讓時間縮短為O(n)，也是十分不錯的呢！）
然後每次按分層規矩（註意，這裡以結尾為原點建分層圖，是由高的層流向比他低一層的層）找一條路徑（沒錯，你沒聽錯，就是單路增廣！），從起點出發：
流完後，然後回到起點，找另外一條流完，就結束了？
比如這張：
下麵一條可行路徑就因為———（兒童不宜）的關係流不過去了（分層有時會導致兩個相鄰點層數相同）。。。
所以，ISAP的精華！出來吧！
詢問？詢問什麼？就是找與他相連的點（邊要有流量）中層數最小的，之後，它就可以變身成比這個編號大一層的點，繼續為流量做貢獻！（在一個點找不到下一個點時，就調整這個點的標記）
改完之後：
就這樣解決了呢！（只需要在s的層數大於點數就可以退出了）
呵呵
上代碼:
不！不！不！太慢了！
我們會發現一件事，如果一種數字的編號消失，就永遠消失了，如果消失，路徑少一編號就不行了，也可以退出！（可以用num記錄每一編號的個數，在每次調整標記時判斷）
耶！一頓操作猛如虎！（這叫斷層優化）
證明（斷層優化）：
設當前編號為x的數沒了，設y=x-1，那麼，編號為y的點有沒有可能變為x呢？首先，如果經過了x，那麼s的層數≥x，且這個為最短的路徑，也就說後面的s的編號都≥x，那麼每條路經中必須有個x。
但x沒了，也就需要一些點來與y的點連接變成x，但是，如果有的話，這些點的層數在作分層時，就已經等於x了（想想看，為什麼不可能小於x（其實就是懶得寫）），那麼路徑就不會產生斷層（矛盾）！
所以斷層優化成立，但是必須基於編號最小的基礎上！
講得好爛。。。
然後，上！代碼。。。
include
include
include
using namespace std;
struct node
{
int y,c,next,other;
}a[210000];int len,last[210000],n,m,st,ed;
void ins(int x,int y,int c)
{
len++;
a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
len++;
a[len].y=x;a[len].c=0;a[len].next=last[y];last[y]=len;
a[len].other=len-1;a[len-1].other=len;
}//建邊
int h[210000]/層數/,num[210000]/斷層優化/,cur[210000]/弧優化/,qian[210000]/保留前一個點到達這裡的邊的編號/;
int list[210000],head,tail;
void bt()
{
head=1;tail=2;num[h[ed]=1]++;list[head]=ed;
while(head!=tail)
{
int x=list[head];
for(int k=last[x];k;k=a[k].next)
{
int y=a[k].y,kl=a[k].other;
if(a[kl].c>0 && h[y]==0)
{
num[h[y]=h[x]+1]++;
list[tail++]=y;
}
}
head++;
}
if(h[st]==0)h[st]=n+1;/判斷能不能到達終點/
}
int mymin(int x,int y){return x<y?x:y;}
int add()/流量/
{
int now=ed,ans=999999999;
while(now!=st)
{
ans=mymin(ans,a[qian[now]].c);
now=a[a[qian[now]].other].y;
}/找路徑上的最小流量/
now=ed;
while(now!=st)
{
a[qian[now]].c-=ans;a[a[qian[now]].other].c+=ans;
now=a[a[qian[now]].other].y;
}/減流/
return ans;
}
int findflow()
{
int ans=0,now=st;
bt();
while(h[st]<=n)
{
bool bk=true;
while(bk==true)/判斷走不走得通/
{
bk=false;
for(int &k=cur[now];k;k=a[k].next)//想想這的當前弧為何長這樣
{
int y=a[k].y;
if(a[k].c>0 && h[y]+1==h[now])
{
bk=true;
qian[y]=k;
now=y;
break;/記錄/
}
}
if(now==ed)
{
ans+=add();now=st;
}/增值/
}
int minn=n;
for(int k=last[now];k;k=a[k].next)
{
if(a[k].c>0)minn=mymin(minn,h[a[k].y]);
}//找層數
if((--num[h[now]])==0)break;//斷層優化
cur[now]=last[now];
num[h[now]=minn+1]++;//更改
if(now!=st)now=a[a[qian[now]].other].y;//想想為什麼這樣打（提示：從是不是最短的路徑上想）
}
return ans;
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&ed);
for(int i=1;i<=m;i++)
{
int x,y,c;scanf("%d%d%d",&x,&y,&c);
ins(x,y,c);
}
for(int i=1;i<=n;i++)cur[i]=last[i];
printf("%d\n",findflow());
return 0;
}
為什麼會快？
其實它比Dinic少了很多沒用的遞歸，讓每次找路徑都有作用，而且用標記省了bfs的時間，所以，只要不被惡意卡掉，ISAP整體上比Dinic要優秀！
註：上面的圖片侵權抱歉！
