记录编号 |
86393 |
评测结果 |
AAAAAAAAAAAAAAAAAAAA |
题目名称 |
[NOIP 2000]方格取数 |
最终得分 |
100 |
用户昵称 |
cstdio |
是否通过 |
通过 |
代码语言 |
C++ |
运行时间 |
0.000 s |
提交时间 |
2014-01-25 18:17:42 |
内存使用 |
0.00 MiB |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iomanip>
#include<queue>
#include<deque>
using namespace std;
const int SIZEN=5010,INF=0x7fffffff;
class EDGE{
public:
int from,to,cap,flow,cost;
};
vector<EDGE> edges;
vector<int> c[SIZEN];//邻接表
int N;//范围是从0到N
void addedge(int from,int to,int cap,int cost){
edges.push_back((EDGE){from,to,cap,0,cost});
edges.push_back((EDGE){to,from,0,0,-cost});
int tot=edges.size()-2;
c[from].push_back(tot);
c[to].push_back(tot+1);
}
int anscost=0;
bool SPFA(int S,int T){
queue<int> Q;
bool inq[SIZEN]={0};
int f[SIZEN]={0};
int father[SIZEN]={0};
int i,x;
for(i=0;i<=N;i++) f[i]=-INF;
f[S]=0,inq[S]=true,Q.push(S);
while(!Q.empty()){
x=Q.front();inq[x]=false;Q.pop();
for(i=0;i<c[x].size();i++){
EDGE& e=edges[c[x][i]];
if(e.cap<=e.flow) continue;
if(f[x]+e.cost>f[e.to]){
f[e.to]=f[x]+e.cost;
father[e.to]=c[x][i];
if(!inq[e.to]){
inq[e.to]=true;
Q.push(e.to);
}
}
}
}
int minf=INF;
x=T;
while(x!=S){
EDGE& e=edges[father[x]];
minf=min(minf,e.cap-e.flow);
x=e.from;
}
anscost+=minf*f[T];
x=T;
int now;
while(x!=S){
now=father[x];
edges[now].flow+=minf;
edges[now^1].flow-=minf;
x=edges[now].from;
}
return true;
}
void MCMF(int S,int T){
SPFA(S,T);
SPFA(S,T);
printf("%d\n",anscost);
}
//下标从0开始
int S,T;
const int SIZEW=51;
int H,W;//H行W列
int board[SIZEW][SIZEW]={0};
int hash(int x,int y){
return x*W+y;
}
void init(void){
scanf("%d",&H);
W=H;
S=hash(0,0);
T=hash(H-1,W-1)+W*H;
N=T;
//左上角的"起点"是0,右下角的"终点"是N
//for(int i=0;i<H;i++) for(int j=0;j<W;j++) scanf("%d",&warm[i][j]);
while(true){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
if(!a) break;
a--,b--;
board[a][b]=w;
}
for(int i=0;i<H;i++){
for(int j=0;j<W;j++){
addedge(hash(i,j),hash(i,j)+W*H,1,board[i][j]);
addedge(hash(i,j),hash(i,j)+W*H,INF,0);
}
}
//+W*H以后就是出点
for(int i=0;i<H;i++) for(int j=0;j<W-1;j++) addedge(hash(i,j)+W*H,hash(i,j+1),INF,0);
for(int i=0;i<H-1;i++) for(int j=0;j<W;j++) addedge(hash(i,j)+W*H,hash(i+1,j),INF,0);
}
int main(){
freopen("fgqs.in","r",stdin);
freopen("fgqs.out","w",stdout);
init();
MCMF(S,T);
return 0;
}