代码:
#include<bits/stdc++.h>
using namespace std;
const int INF=INT_MAX;
int n,m,head[110]={0},d[110]={0},cnt=0,ans=0;
queue<int> q;
struct Edge{
int to,nxt,cap,flow;
}e[10001];
void add(int u,int v,int w){
e[++cnt].to=v;
e[cnt].cap=w;
e[cnt].flow=0;
e[cnt].nxt=head[u];
head[u]=cnt;
}
void init(){
memset(d,0,sizeof(d));
while(!q.empty()) q.pop();
}
bool bfs(int s,int t){
init();
d[s]=1,q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(d[v]==0 && e[i].cap>e[i].flow){
d[v]=d[u]+1,q.push(v);
if(v==t) return true;
}
}
}
return false;
}
int dfs(int u,int flow,int t){
if(u==t) return flow;
int rest=flow;
for(int i=head[u];i>0 && rest>0;i=e[i].nxt){
int v=e[i].to;
if(d[v]==d[u]+1 && e[i].cap>e[i].flow){
int k=dfs(v,min(rest,e[i].cap-e[i].flow),t),j=(i%2==1)?(i+1):(i-1);
if(k==0) d[v]=0;
e[i].flow+=k,e[j].flow-=k;
rest-=k;
}
}
return flow-rest;
}
int Dinic(int s,int t){
int ans=0;
while(bfs(s,t)==true) ans+=dfs(s,INF,t);
return ans;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=2;i<=n+1;i++){
int x;
scanf("%d",&x);
add(1,i,x),add(i,1,0);
ans+=x;
char tools[10000];
memset(tools,0,sizeof tools);
cin.getline(tools,10000);
int ulen=0,tool;
while (sscanf(tools+ulen,"%d",&tool)==1)//之前已经用scanf读完了赞助商同意支付该实验的费用
{//tool是该实验所需仪器的其中一个
//这一行,你可以将读进来的编号进行储存、处理,如连边。
add(i,tool+n+1,INF),add(tool+n+1,i,INF);
if (tool==0)
ulen++;
else {
while (tool) {
tool/=10;
ulen++;
}
}
ulen++;
}
}
for(int i=n+2;i<=n+m+1;i++){
int x;
scanf("%d",&x);
add(i,n+m+2,x),add(n+m+2,i,0);
}
ans-=Dinic(1,n+m+2);
for(int i=2;i<=n+1;i++) if(d[i]>0) printf("%d ",i-1);
printf("\n");
for(int i=n+2;i<=n+m+1;i++) if(d[i]>0) printf("%d ",i-(n+1));
printf("\n%d",ans);
return 0;
}
读入直接用题目的了,看讨论区说输出很阴间。
太伞兵了迷惑 11 分