- 科技
- Codeforces237 E.Build String（费用流）
题意：
数据范围：
解法：
最小费用最大流
.
源点S汇点T
,
源点对目标串的每个字母连边
,cap
=字母个数
,cost
=0,
目标串的每个字母ch对n个串都连边
,cap
[i
]=第i个串的ch个数
,cost
=i
,
n个串对汇点连边
,cap
=a
[i
],cost
=0.
如果maxflow
=目标串长度
,那么答案为mincost
.
否则无解
,输出
-1.
code：
#include<bits/stdc++.h>
using namespace std
;
const int maxm
=105;
const int N
=2e5+5;
const int M
=2e5+5;
const int inf
=1e9;
struct Node
{
int from
,to
,nt
,cap
,flow
,cost
;
}e
[M
];
int head
[N
],dist
[N
],mark
[N
],pre
[N
],cnt
=1;
int mincost
,maxflow
;
int id
[N
],idx
;
int S_ch
[26];
int S
,T
;
char s
[maxm
][maxm
];
int ch
[maxm
][26];
int a
[maxm
];
int n
;
void add(int from
,int to
,int cap
,int cost
){
e
[++cnt
]={from
,to
,head
[from
],cap
,0,cost
};
head
[from
]=cnt
;
e
[++cnt
]={to
,from
,head
[to
],0,0,-cost
};
head
[to
]=cnt
;
}
bool spfa(){
for(int i
=1;i
<=idx
;i
++){
mark
[i
]=0;
dist
[i
]=inf
;
}
queue
<int>q
;
q
.push(S
);
dist
[S
]=0;
mark
[S
]=1;
while(!q
.empty()){
int x
=q
.front();q
.pop();
mark
[x
]=0;
for(int i
=head
[x
];i
;i
=e
[i
].nt
){
int v
=e
[i
].to
;
if(e
[i
].cap
>e
[i
].flow
&&dist
[v
]>dist
[x
]+e
[i
].cost
){
dist
[v
]=dist
[x
]+e
[i
].cost
;
pre
[v
]=i
;
if(!mark
[v
]){
mark
[v
]=1;
q
.push(v
);
}
}
}
}
return dist
[T
]!=inf
;
}
void ek(){
while(spfa()){
int k
=inf
;
for(int i
=T
;i
!=S
;i
=e
[pre
[i
]].from
){
k
=min(k
,e
[pre
[i
]].cap
-e
[pre
[i
]].flow
);
}
for(int i
=T
;i
!=S
;i
=e
[pre
[i
]].from
){
e
[pre
[i
]].flow
+=k
;
e
[pre
[i
]^1].flow
-=k
;
}
maxflow
+=k
;
mincost
+=k
*dist
[T
];
}
}
signed main(){
scanf("%s",s
[0]);
scanf("%d",&n
);
for(int i
=1;i
<=n
;i
++){
scanf("%s",s
[i
]);
scanf("%d",&a
[i
]);
}
for(int i
=0;i
<=n
;i
++){
int len
=strlen(s
[i
]);
for(int j
=0;j
<len
;j
++){
ch
[i
][s
[i
][j
]-'a']++;
}
}
S
=++idx
;
T
=++idx
;
for(int i
=0;i
<26;i
++){
S_ch
[i
]=++idx
;
add(S
,S_ch
[i
],ch
[0][i
],0);
}
for(int i
=1;i
<=n
;i
++){
id
[i
]=++idx
;
for(int j
=0;j
<26;j
++){
if(!ch
[i
][j
])continue;
add(S_ch
[j
],id
[i
],ch
[i
][j
],i
);
}
add(id
[i
],T
,a
[i
],0);
}
ek();
if(maxflow
!=strlen(s
[0])){
puts("-1");
}else{
printf("%d\n",mincost
);
}
return 0;
}
Processed:
0.021, SQL:
8
