不妨令 \(k=m-k\)，那么题目的意思就是至多删去 \(k\) 条边。
首先二分答案 \(t\)，然后求最少需要删去多少的边，如果最少需要删去的边 \(\leq k\) 则合法。
在原图中统计每一个点的入度-出度，记为 \(d_u\)。
首先对于每一条边 \((u,v)\)，从 \(u\) 向 \(v\) 连边 \(\big([0,1],1\big)\)（小括号内前一位表示容量上下界，后一位表示费用），表示删去这条边需要耗费 \(1\)。
对于每一个点 \(u\)，分三种情况讨论：
-
若 \(d_u>t\)，那么 \(d_u\) 需要减少至少 \(d_u-t\)，至多 \(d_u+t\)，即 \(u\) 的入度需要减少 \([d_u-t,d_u+t]\)。
那么我们从 \(u\) 向 \(T\) 连边 \(\big([d_u-t,d_u+t],0\big)\)，表示需要删除连向 \(u\) 的这么多边。
注意这种方案也是可行的：先让 \(d_u\) 增加一些，再让 \(d_u\) 减少更多。但由于贪心的原因，如果有这种情况出现，我们明显有更优的方案而不选择删掉那么多边，所以我们不考虑这种情况。下面同理，我就不一一解释了。
-
若 \(d_u<-t\)，同理，我们从 \(S\) 向 \(u\) 连边 \(\big([-t-d_u,t-d_u],0\big)\)，表示需要删除从 \(u\) 出发的这么多边。
-
若 \(-t\leq d_u \leq t\)，那么我们从 \(u\) 向 \(T\) 连边 \(\big([0,d_u+t],0\big)\)，表示我们可以删除连向 \(u\) 的这么多边；从 \(S\) 向 \(u\) 连边 \(\big([0,t-d_u],0\big)\)，表示我们可以删除从 \(u\) 出发的这么多边。
然后跑最小费用最大流即可，若满流且最小费用 \(\leq k\)，则证明 \(t\) 可行。
代码如下：
#include<cstdio>
#include<iostream>
#include<queue>
#include<map>
#include<cstring>
#include<cmath>
#define N 55
#define INF 0x7fffffff
using namespace std;
struct Edge
{
int u,v;
Edge(){};
Edge(int a,int b){u=a,v=b;}
}e[N*N];
int T,n,m,k,tot,deg[N];
int s,t,ss,tt,add[N];
int cnt,head[N],to[N*6+N*N*2],c[N*6+N*N*2],w[N*6+N*N*2],nxt[N*6+N*N*2];
int maxflow,mincost,dis[N],pre[N];
bool inq[N];
map<string,int>mp;
queue<int>q;
void adde(int u,int v,int ci,int wi)
{
to[++cnt]=v;
c[cnt]=ci;
w[cnt]=wi;
nxt[cnt]=head[u];
head[u]=cnt;
to[++cnt]=u;
c[cnt]=0;
w[cnt]=-wi;
nxt[cnt]=head[v];
head[v]=cnt;
}
bool SPFA()
{
memset(dis,127,sizeof(dis));
q.push(ss);
dis[ss]=0;
inq[ss]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
inq[u]=0;
for(int i=head[u];i;i=nxt[i])
{
int v=to[i];
if(c[i]&&dis[u]+w[i]<dis[v])
{
dis[v]=dis[u]+w[i];
pre[v]=i;
if(!inq[v])
{
q.push(v);
inq[v]=1;
}
}
}
}
return dis[tt]!=dis[0];
}
void MCMF()
{
maxflow=mincost=0;
while(SPFA())
{
int minflow=INF;
for(int u=tt;u!=ss;u=to[pre[u]^1]) minflow=min(minflow,c[pre[u]]);
for(int u=tt;u!=ss;u=to[pre[u]^1])
{
c[pre[u]]-=minflow;
c[pre[u]^1]+=minflow;
mincost+=w[pre[u]]*minflow;
}
maxflow+=minflow;
}
}
bool check(int mid)
{
cnt=1;
memset(head,0,sizeof(head));
memset(add,0,sizeof(add));
for(int i=1;i<=m;i++)
adde(e[i].u,e[i].v,1,1);
for(int i=1;i<=n;i++)
{
if(deg[i]>mid)
{
add[i]-=deg[i]-mid,add[t]+=deg[i]-mid;
adde(i,t,mid*2,0);
}
else if(deg[i]<-mid)
{
add[s]-=-mid-deg[i],add[i]+=-mid-deg[i];
adde(s,i,mid*2,0);
}
else
{
adde(s,i,mid-deg[i],0);
adde(i,t,deg[i]+mid,0);
}
}
int sum=0;
for(int i=1;i<=t;i++)
{
if(add[i]<0) adde(i,tt,-add[i],0);
else adde(ss,i,add[i],0),sum+=add[i];
}
adde(t,s,INF,0);
MCMF();
if(maxflow==sum) return mincost<=k;
return false;
}
int main()
{
scanf("%d",&T);
for(int nowT=1;nowT<=T;nowT++)
{
tot=0;
mp.clear();
memset(deg,0,sizeof(deg));
scanf("%d%d%d",&n,&m,&k);
k=m-k;
s=n+1,t=s+1,ss=t+1,tt=ss+1;
for(int i=1;i<=m;i++)
{
string a,b;
cin>>a>>b;
if(!mp[a]) mp[a]=++tot;
if(!mp[b]) mp[b]=++tot;
e[i]=Edge(mp[a],mp[b]);
deg[mp[a]]--,deg[mp[b]]++;
}
int l=0,r=0,ans=0;
for(int i=1;i<=n;i++)
r=max(r,abs(deg[i]));
while(l<=r)
{
int mid=(l+r)>>1;
if(check(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
printf("Case #%d:\n%d\n",nowT,ans);
}
return 0;
}