最開(kāi)始寫費(fèi)用流的時(shí)候，有且只會(huì)SPFA版的費(fèi)用流，而且一直都?jí)蛴茫话銇?lái)說(shuō)只要建出了圖就贏了，網(wǎng)絡(luò)流怎么都不會(huì)超時(shí)。
。。。。這個(gè)情況到今天被終結(jié)了。。。
終結(jié)者見(jiàn)下：
--------------------------------------------------------------------------------------------------------
最優(yōu)圖像
【題目描述】
小E在好友小W的家中發(fā)現(xiàn)一幅神奇的圖畫，對(duì)此頗有興趣。它可以被看做一個(gè)包含N×M個(gè)像素的黑白圖像，為了方便起見(jiàn)，我們用0表示白色像素，1表示黑色像素。小E認(rèn)為這幅圖畫暗藏玄機(jī)，因此他記錄下了這幅圖像中每行、每列的黑色像素?cái)?shù)量，以回去慢慢研究其中的奧妙。
有一天，小W不慎將圖畫打濕，原本的圖像已經(jīng)很難分辨。他十分著急，于是找來(lái)小E，希望共同還原這幅圖畫。根據(jù)打濕后的圖畫，他們無(wú)法確定真正的圖像，然而可以推測(cè)出每個(gè)像素原本是黑色像素的概率Pij%。那么，一個(gè)完整的圖像的出現(xiàn)概率就可以定義為 
，其中Sij表示在還原后的圖像中，像素是白色(0)還是黑色(1)。換句話說(shuō)，一個(gè)完整圖像出現(xiàn)概率就等于其所有黑色像素的出現(xiàn)概率之積。顯然，圖像的黑色像素不能包含概率為0的像素。
然而，小E對(duì)此也無(wú)能為力。因此他們找到了會(huì)編程的小F，也就是你，請(qǐng)你根據(jù)以上信息，告訴他們最有可能是原始圖像的答案是什么。
【輸入文件】
輸入文件image.in的第一行是兩個(gè)正整數(shù)N和M，表示圖像大小。
接下來(lái)N行每行包含M個(gè)整數(shù)，表示每個(gè)像素是黑色像素的概率為Pij%。0 ≤ Pij < 100。
接下來(lái)一行有N個(gè)非負(fù)整數(shù)，表示每一行中黑色像素的個(gè)數(shù)。
接下來(lái)一行有M個(gè)非負(fù)整數(shù)，表示每一列中黑色像素的個(gè)數(shù)。
【輸出文件】
輸出文件image.out包含一個(gè)N×M的01矩陣，表示你還原出的圖像。輸出不包含空格。圖像每行、每列中1的個(gè)數(shù)必須與輸入一致，且是所有可能的圖像中出現(xiàn)概率最大的一個(gè)。輸入數(shù)據(jù)保證至少存在一個(gè)可能的圖像。如果有多種最優(yōu)圖像，任意輸出一種即可。
【樣例輸入】
2 2
90 10
20 80
1 1
1 1
【樣例輸出】
10
01
【樣例解釋】
共有兩種可能的圖像：
01
10
和
10
01
前者的出現(xiàn)概率是0.1×0.2=0.02，后者的出現(xiàn)概率是0.9×0.8=0.72，故后者是最優(yōu)圖像。
【數(shù)據(jù)規(guī)模和約定】
對(duì)于20%的數(shù)據(jù)，N , M ≤ 5；
對(duì)于100%的數(shù)據(jù)，N , M ≤ 100。
--------------------------------------------------------------------------------------------------------
這道題的時(shí)限是兩秒。
這道題的做法是把行和列拿出來(lái)，如果i行j列出現(xiàn)1的就把i行與j列連一條流量為1，費(fèi)用為log(p[i][j])的邊。源與每行、每列與匯都連一條流量為行、列1的個(gè)數(shù)，費(fèi)用為0的邊，然后求最大費(fèi)用最大流。流過(guò)的邊所連的行和列的交點(diǎn)就有一個(gè)點(diǎn)。
當(dāng)時(shí)看到n<=100，總點(diǎn)數(shù)就是2n，心想很小。。。但沒(méi)想到邊有10000條，用SPFA寫出來(lái)了過(guò)后開(kāi)始只有60分。。后來(lái)優(yōu)化到了70分，就是SPFA極限了，剩下的點(diǎn)根本進(jìn)不了2秒。
SPFA的時(shí)間復(fù)雜度是O(km)的，m是邊數(shù)，k是常數(shù)，在這題特殊的圖里面一次只能增廣1的流量。。所以總的時(shí)間復(fù)雜度達(dá)到了O(100*100*O(SPFA)) > 100000000。。。
于是沒(méi)辦法，把zkw的網(wǎng)絡(luò)流學(xué)了。。
其實(shí)zkw網(wǎng)絡(luò)流增廣的時(shí)候是sap，修改標(biāo)號(hào)的時(shí)候是KM。。。。所以學(xué)起來(lái)很順暢，寫起來(lái)也比SPFA的短，但是效率要高很多：
膜拜啊！
代碼：
1
/**//*
2
* $File: costflow.cpp
3
*/
4
5#include <iostream>
6#define MAXNODE 500
7#define MAXEDGE MAXNODE*MAXNODE
8#define MIN(a,b) ((a)<(b)?(a):(b))
9#define OPPOSITE(x) (((x)&1)?((x)+1):((x)-1))
10 #define INFINIT ~0U>>1
11
12using namespace std;
13
14
15int n,m;
16int N,S,T;
17int begin[MAXNODE+1],end[MAXEDGE+1],next[MAXEDGE+1],c[MAXEDGE+1],cost[MAXEDGE+1],d[MAXNODE+1],cur[MAXNODE+1];
18bool hash[MAXNODE+1];
19int Count = 0;
20int aug(int u,int f)
{
21 if (u == T) return f;
22 hash[u] = true;
23 for (int now = cur[u]; now; now = next[now])
24 if (c[now]&&!hash[end[now]]&&d[u] == d[end[now]]+cost[now])
25 if (int tmp = aug(end[now],MIN(f,c[now])))
26 return c[now] -= tmp,c[OPPOSITE(now)] += tmp,cur[u] = now,tmp;
27 return 0;
28}
29bool modlabel(){
30 int tmp = INFINIT;
31 for (int i = 1; i<=N; i++)
32 if (hash[i])
33 for (int now = begin[i]; now; now = next[now])
34 if (c[now]&&!hash[end[now]])
35 tmp = MIN(tmp,d[end[now]]+cost[now]-d[i]);
36 if (tmp == INFINIT)
37 return true;
38 for (int i = 1; i<=N; i++)
39 if (hash[i])
40 hash[i] = false,d[i] += tmp;
41 return false;
42}
43int CostFlow(){
44 int costflow = 0,tmp;
45
while (true){
46 for (int i = 1; i<=N; i++)
47 cur[i] = begin[i];
48 while (tmp = aug(S,~0U>>1)){
49 costflow += tmp*d[S];
50 memset(hash,0,sizeof(hash));
51
}
52 if (modlabel())
53 break;
54 }
55 return costflow;
56}
57void AddEdge(int a,int b,int flow, int v){
58 Count++; next[Count] = begin[a]; begin[a] = Count; end[Count] = b; c[Count] = flow; cost[Count] = v;
59 Count++; next[Count] = begin[b]; begin[b] = Count; end[Count] = a; c[Count] = 0; cost[Count] = -v;
60}
61int main(){
62 freopen("costflow.in","r",stdin);
63 freopen("costflow.out","w",stdout);
64 scanf("%d%d",&n,&m);
65 while (m--){
66 int t1,t2,t3,t4;
67 scanf("%d%d%d%d",&t1,&t2,&t3,&t4);
68 AddEdge(t1,t2,t3,t4);
69 }
70 S = 1,T = N = n;
71 printf("%d\n",CostFlow());
72 return 0;
73}
74
75
今天先休息一下，整理一下思路有時(shí)間再詳細(xì)寫下過(guò)程~