我感觉我的思路和题解是一样的,可是为什么会T在#3呢??
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#define N 50
#define M 80050
#define inf (1<<25)
using namespace std;
int n,m,p[N],a[105][N],tot=1,t,sum,mincost;
int d[M],pre[M],h[M];
bool vis[M];
vector<int> g[M];
queue<int> q;
struct edge{
int to,w,c;
} e[10000005];
int qread(){
int num=0; char ch=getchar();
while(ch<'0' || ch>'9') ch=getchar();
while(ch>='0' && ch<='9') {
num=num*10+ch-'0';
ch=getchar();
}
return num;
}
void addedge(int x,int y,int w,int c){
e[++tot].to=y; e[tot].w=w; e[tot].c=c; g[x].push_back(tot);
e[++tot].to=x; e[tot].w=0; e[tot].c=-c; g[y].push_back(tot);
}
bool spfa(){
memset(d,0x3f,sizeof(d));
d[0]=0; q.push(0);
while(!q.empty())
{
int u=q.front(); q.pop(); vis[u]=0;
for(int i=0; i<g[u].size(); ++i)
{
int tag=g[u][i],v=e[tag].to,w=e[tag].w,c=e[tag].c;
if(!w || d[v] <= d[u]+c) continue;
d[v] = d[u]+c;
pre[v] = tag;
if(!vis[v])
{
vis[v]=1;
q.push(v);
}
}
}
return d[t] < 1000000000;
}
// num = (times-1)*m+i
void update()
{
int point=t;
mincost+=d[t];
while(point)
{
point=pre[point];
--e[point].w;
++e[point^1].w;
point=e[point^1].to;
if(1 <= point && point <= sum*m)
{
int op=point%m,k=(point-1)/m+1;
if(op==0) op=m;
if(h[op]==k){
++h[op];
for(int i=1; i<=n; ++i)
addedge(k*m+op,sum*m+i,1,(k+1)*a[op][i]);
addedge(0,k*m+op,1,0);
}
}
}
}
int main(){
n=qread(); m=qread();
for(int i=1; i<=n; ++i){
p[i]=qread();
sum+=p[i];
}
t=sum*m+n+1;
for(int i=1; i<=n; ++i){
addedge(sum*m+i,t,p[i],0);
for(int j=1; j<=m; ++j)
a[j][i]=qread();
}
for(int i=1; i<=m; ++i){
h[i]=1;
for(int j=1; j<=n; ++j)
addedge(i,sum*m+j,1,a[i][j]);
addedge(0,i,1,0);
}
while(spfa()) update();
printf("%d",mincost);
return 0;
}