题面
https://www.luogu.org/problemnew/show/P2050
题解
费用流 + 动态加点,
- #include
- #include
- #include
- #include
- #include
- #include
- #define LL long long
- #define N 2000
- #define INF 1000000007
- #define S 0
- #define T (sumn+m+1)
- #define ri register int
- using namespace std;
- int n,m,sumn,cc;
- int typ[N],cai[N];
- int p[200][200];
- struct graph {
- vector to,w,c;
- vector ed[N];
- LL dis[N]; int cur[N];
- bool vis[N];
- void add_edge(int a,int b,int aw,int ac) {
- to.push_back(b); w.push_back(aw); c.push_back(ac); ed[a].push_back(to.size()-1);
- to.push_back(a); w.push_back(0); c.push_back(-ac); ed[b].push_back(to.size()-1);
- }
- bool spfa() {
- memset(dis,0x2f,sizeof(dis));
- memset(vis,0,sizeof(vis));
- queue q;
- dis[S]=0;q.push(S);vis[S]=1;
- while (!q.empty()) {
- int x=q.front(); q.pop();
- for (ri i=0;i<ed[x].size();i++) {
- int e=ed[x][i];
- if (dis[to[e]]>dis[x]+c[e] && w[e]) {
- dis[to[e]]=dis[x]+c[e];
- if (!vis[to[e]]) vis[to[e]]=1,q.push(to[e]);
- }
- }
- vis[x]=0;
- }
- return dis[T]<INF;
- }
- int dfs(int x,int lim) {
- if (!lim) return lim;
- LL sum=0; vis[x]=1;
- for (ri &i=cur[x];i<ed[x].size();i++) {
- int e=ed[x][i];
- if (dis[x]+c[e]==dis[to[e]] && w[e] && !vis[to[e]]) {
- int f;
- if (to[e]==T) {
- //puts("54");
- f=lim; ++cc; typ[cc]=typ[x];
- for (ri j=0;j<ed[x].size();j++) {
- int je=ed[x][j];
- if (je%2==1) {
- add_edge(to[je],cc,1,c[je^1]+p[cai[to[je]]][typ[cc]]);
- //cout<<-c[je]+p[cai[to[je]]][typ[cc]]<
- }
- }
- add_edge(cc,T,1,0);
- }
- else
- f=dfs(to[e],min(lim,w[e]));
- w[e]-=f; w[1^e]+=f;
- lim-=f; sum+=f;
- if (!lim) return sum;
- }
- }
- return sum;
- }
- LL zkw() {
- LL ret=0;
- while (spfa()) {
- memset(vis,0,sizeof(vis));
- memset(cur,0,sizeof(cur));
- ret+=dfs(S,INF)*dis[T];
- }
- return ret;
- }
- } G;
- int main() {
- int x;
- scanf("%d %d",&n,&m);
- sumn=0;
- for (ri i=1;i<=n;i++) {
- scanf("%d",&x);
- cai[i]=i;
- G.add_edge(S,i,x,0);
- }
- sumn=n;
- for (ri i=1;i<=n;i++)
- for (ri j=1;j<=m;j++) scanf("%d",&p[i][j]);
- for (ri i=1;i<=m;i++) {
- G.add_edge(sumn+i,T,1,0);
- typ[sumn+i]=i;
- }
- for (ri i=1;i<=sumn;i++)
- for (ri j=1;j<=m;j++) G.add_edge(i,sumn+j,1,p[cai[i]][j]);
- cc=T;
- cout<<G.zkw()<<endl;
- }
来源: http://www.bubuko.com/infodetail-3129283.html