hdu4862 2014多校B題/ 費用流（最優情況下用不大於K條路徑覆蓋）（不同的解法）
題意： 一個數字矩陣，可以出發K次，每次可以從右邊或者下面走，要求（在收益最大情況下）覆蓋全圖，不能則輸出-1。（規則：每次跳一步的時候若格子數字相等則獲得該數字的能量，每跳一步消耗距離的能量）。每個格子走且僅能走一次。
選<=K條路徑，最優情況來覆蓋全圖。
顯然用拆點為二分圖。
一種解法：邊（流量，費用）
源點向X部連邊（1,0）Y部向匯點連邊（1,0）X到Y，若能到，則有邊（1，消耗-獲得）。關鍵點（解決每個點都覆蓋，恰好起到填補的作用）：在X部最上面添加一個點，源點連之（k,0）它向所有Y點連邊（1,0）。跑最小費用最大流即可。
第二種：（感想zz1215提供的建圖思路）
源點向X部連邊（1,0）Y部向匯點連邊（1,0）,Y到X，若能到，則有邊（1，消耗-獲得）(注意這裡是回流)，每個點I-->I`有邊（1，-w_inf），這裡的w_inf為相對大數，只要保證該費用較“小”即可（相對其他費用，他是最廉價的，這樣必優先流這條邊。添加超級源點，向源點連邊（K,0）。增廣K次中，若一直增大，則取最大，否則到開始下降的時候要BREAK。（先曾後減的）。
PS:開始時候因為定位編號搞錯有沒有！編號（i,j）=i*m+j,而不是i*n+j！！！
圖：
<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tPrC66O6PC9wPgo8cD48cHJlIGNsYXNzPQ=="brush:java;">#include //24ms
#include
#include
#include
#include
using namespace std;
int n,m,k;
const int inf=0x3f3f3f3f;
int a[25][25];
int head[500];int e[10000][4];int nume=0;
void inline adde(int i,int j,int c,int w)
{
e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;
e[nume][2]=c;e[nume++][3]=w;
e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;
e[nume][2]=0;e[nume++][3]=-w;
}
int inq[500];int d[500];
bool spfa(int &sumcost)
{
for(int i=0;i<=2*n*m+3;i++)
{
inq[i]=0;d[i]=inf;
}
int minf=inf;
queueq;
int prv[300];int pre[300];
q.push(2*n*m+2);
inq[2*n*m+2]=1;
d[2*n*m+2]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();inq[cur]=0;
for(int i=head[cur];i!=-1;i=e[i][1])
{
int v=e[i][0];
if(e[i][2]>0&&d[v]>e[i][3]+d[cur])
{
d[v]=e[i][3]+d[cur];
prv[v]=cur;
pre[v]=i;
if(!inq[v])
{
q.push(v);
inq[v]=1;
}
}
}
}
if(d[2*n*m+1]==inf)return 0;
int cur=2*n*m+1;
while(cur!=2*n*m+2)
{
minf=min(minf,e[pre[cur]][2]);
cur=prv[cur];
}
cur=2*n*m+1;
while(cur!=2*n*m+2)
{
e[pre[cur]][2]-=minf;e[pre[cur]^1][2]+=minf;
cur=prv[cur];
}
sumcost+=d[2*n*m+1]*minf;
return 1;
}
int mincost()
{
int sum=0;
while(spfa(sum));
return sum;
}
void init()
{
nume=0;
for(int i=0;i<=2*n*m+3;i++)
{
head[i]=-1;
}
}
int main()
{
int T;
scanf("%d",&T);
for(int iii=1;iii<=T;iii++)
{
scanf("%d%d%d",&n,&m,&k);
init();
string s;
for(int i=0;i>s;
for(int j=0;jk)
{
printf("-1\n");continue;
}
for(int i=0;i%d:c:%d,w:%d\n",i,e[j][0],e[j][2],e[j][3]);*/
printf("%d\n",-mincost());
}
return 0;
}
方法二：
#include //31ms
#include
#include
#include
using namespace std;
int n,m,k;
const int inf=0x3f3f3f3f;
const int winf=100000;
int a[25][25];
int head[500];int e[20001][4];int nume=0;
void inline adde(int i,int j,int c,int w)
{
e[nume][0]=j;e[nume][1]=head[i];head[i]=nume;
e[nume][2]=c;e[nume++][3]=w;
e[nume][0]=i;e[nume][1]=head[j];head[j]=nume;
e[nume][2]=0;e[nume++][3]=-w;
}
int inq[500];int d[500];
bool spfa(long long &sumcost)
{
for(int i=0;i<=2*n*m+3;i++)
{
inq[i]=0;d[i]=inf;
}
int prv[500];int pre[500];
int minf=inf;
queueq;
q.push(n*m);
inq[n*m]=1;
d[n*m]=0;
while(!q.empty())
{
int cur=q.front();
q.pop();
inq[cur]=0;
for(int i=head[cur];i!=-1;i=e[i][1])
{
int v=e[i][0];
if(e[i][2]>0&&d[v]>e[i][3]+d[cur])
{
d[v]=e[i][3]+d[cur];
prv[v]=cur;
pre[v]=i;
if(!inq[v])
{
q.push(v);
inq[v]=1;
}
}
}
}
if(d[2*n*m+1]==inf)return 0;
int cur=2*n*m+1;
while(cur!=n*m)
{
minf=min(minf,e[pre[cur]][2]);
cur=prv[cur];
}
cur=2*n*m+1;
while(cur!=n*m)
{
e[pre[cur]][2]-=minf;
e[pre[cur]^1][2]+=minf;
cur=prv[cur];
}
sumcost+=d[2*n*m+1]*(long long)minf;
return 1;
}
long long mincost()
{
long long sum=0;
long long lastsum=0;
while(spfa(sum)) //變小的時候跳出
{
if(lastsum>=-sum){return -lastsum;}
lastsum=-sum;
}
return sum;
}
void init()
{
nume=0;
for(int i=0;i<=2*n*m+3;i++)
{
head[i]=-1;
}
}
int main()
{
int T;
scanf("%d",&T);
for(int iii=1;iii<=T;iii++)
{
scanf("%d%d%d",&n,&m,&k);
init();
string s;
for(int i=0;i>s;
for(int j=0;jk)
{
printf("-1\n");continue;
}
for(int i=0;i%d:c:%d,w:%d\n",i,e[j][0],e[j][2],e[j][3]);*/
cout<<-mincost()-n*m*winf<
