CCF201812-5
CCF201812-5 管道清洁
Description
\[ n\leq 200,m\leq 500 \]
Sample (4 in Total)
Sample Input
3 0 1
4 4
1 2 A
2 3 B
3 4 C
4 1 D
5 7
1 2 B
2 3 B
3 1 D
2 4 A
4 3 C
1 5 C
5 2 D
5 7
1 2 B
2 3 B
3 1 C
2 4 A
4 3 D
1 5 C
5 2 DSample Output
4
-1
8Explaination
Solution
从1开始到1结束，说明走的路径是一（多）个环。
看成无向图后只走A和B时图是连通的，说明这个环可以不用过1。（即无源汇）
然后分析四种有向边，需要被清理说明下界是1，不需要就是0；可以被多次走过说明上界是INF，不可以就是1。（即要求图的可行流）
然后可能要吃包子，综合一下就是求无源汇可行费用流了。
通过是否满流判断是否有解；通过费用流的cost来记录最小花费。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 210;
const int INF = 1e9+7;
typedef long long ll;
int le,ri,cnt,sum,val;val为包子，0/1；cnt为每条边均流最小流时的流量标量和，sum为虚拟源点总流出流量。即1->2 A,2->3 A时，sum为1，cnt为2
黑盒(费用流实现)
struct MCMF{
struct Edge{
int from,to,cap,cost;
Edge(){}
Edge(int from,int to,int cap,int cost):from(from),to(to),cap(cap),cost(cost){}
};
int n,m,s,t;
vector<Edge> edges;
vector<int> G[maxn];
int inq[maxn];//inqueue
int d[maxn];//dis
int p[maxn];//pre
int a[maxn];//flow
void init()
{
sum=cnt=0;
for(int i=0;i<=n;++i) G[i].clear();
edges.clear();
}
void AddEdge(int from,int to,int cap,int cost)
{
edges.push_back(Edge(from,to,cap,cost));
edges.push_back(Edge(to,from,0,-cost));
m=edges.size();
G[from].push_back(m-2);
G[to].push_back(m-1);
}
bool BF(int& flow,int& cost)
{
for(int i=0;i<=n;++i) d[i]=INF,inq[i]=0;
d[s]=0,inq[s]=1,p[s]=0,a[s]=INF;
queue<int> Q;
Q.push(s);
while(!Q.empty())
{
int u=Q.front();Q.pop();
inq[u]=0;
//cout<<u<<' '<<G[u].size()<<' '<<d[u]<<'\n';
for(int i=0;i<G[u].size();++i)
{
Edge& e=edges[G[u][i]];
if(e.cap&&d[e.to]>d[u]+e.cost)
{
d[e.to]=d[u]+e.cost;
p[e.to]=G[u][i];
a[e.to]=min(a[u],e.cap);
if(!inq[e.to])
{
Q.push(e.to);
inq[e.to]=1;
}
}
}
}
if(d[t]==INF) return false;
flow+=a[t];
cost+=d[t]*a[t];
int u=t;
while(u!=s)
{
edges[p[u]].cap-=a[t];
edges[p[u]^1].cap+=a[t];
u=edges[p[u]].from;
}
return true;
}
int Mincost()
{
int flow=0,cost=0;
//cout<<m<<endl;
while(BF(flow,cost));
//for(int i=1;i<=10;++i) cout<<i<<' '<<p[i]<<endl;
//cout<<flow<<cnt<<cost<<sum<<endl;
if(flow==sum) return cost;
else return -1;
}
}NF;主程序
inline int read()
{
int x=0;//f;
char ch=getchar();
while(ch<'0'||ch>'9') ch=getchar();
while(ch>='0'&&ch<='9') {x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
return x;
}
inline void readin()
{
int du[maxn]={0};
le=read();
ri=read();
NF.s=0;
NF.n=NF.t=le+1;
for(int i=1;i<=ri;++i)
{
int p=read(),q=read();
char ch;
scanf("%c",&ch);
if(ch=='A')
{
NF.AddEdge(p,q,INF,val);
++du[q],--du[p],++cnt;
}
else if(ch=='B')
{
++du[q],--du[p],++cnt;
}
else if(ch=='C')
{
NF.AddEdge(p,q,INF,val);
}
else
{
NF.AddEdge(p,q,1,val);
}
}
for(int i=1;i<=le;++i)
{
if(du[i]>0) sum+=du[i],NF.AddEdge(NF.s,i,du[i],0);
else if(du[i]<0) NF.AddEdge(i,NF.t,-du[i],0);
}
}
int main()
{
int t=read();
val=read();
val=read();
while(t--)
{
NF.init();
readin();
int p=NF.Mincost();
printf("%d\n",p==-1?p:p+cnt*val);
}
return 0;
}