开始就想着要拆点,i与i‘连边容量为2,费用为矩阵中的值,但是一想就不对了,如果这样的话,每个点可以走两次,每次的费用都是一样的,应该有一次为0才对,所以应该加两条边,容量都是1,一条边的费用为0。然后往左,下连边,,,跑费用流,求出最大的费用。。。
hdu 3376 数据开大些就可以了,N=720010
#include<stdio.h>
#include<string.h>
#include<queue>
const int N=2000;
const int inf=0x3fffffff;
using namespace std;
int dist[N],head[N],num,start,end,n,vis[N],pre[N];
struct edge
{
int......
阅读全文