题意：
给你一个带权有向图，选择一些边组成许多没有公共边的环，使每个点都在k个环上，要求代价最小。
SOL：
现在已经养成了这种习惯，偏题怪题都往网络流上想。。。
怎么做这题呢。。。
对我们看到每个点都在k个环上,而且没有公共边,那么很显然每个点的入度出度都为k. 然后我们拆点,建源汇ST,S与每个入点连边容量为k,出点与汇点相连容量为k,费用为0,如果城市i,j之间有边那么将i的入点和j的出点连一条费用为权,容量为1的边.然后跑一遍费用流.如果每条边都满流那么就有解.
好神奇...从环变成一个二分图...然后从毫无头绪变成一个费用流...又觉得智商被碾压了.
写代码因为spfa的时候出队结点没重置...然后一直wa...日了狗了...
更加理解spfa了....(无奈
Code:
/*==========================================================================
# Last modified: 2016-03-10 20:55
# Filename: uva2197.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector> #define lowbit(x) (x)&(-x)
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define getlc(a) ch[(a)][0]
#define getrc(a) ch[(a)][1] #define maxn 100000
#define maxm 100000
#define pi 3.1415926535898
#define _e 2.718281828459
#define INF 1070000000
using namespace std;
typedef long long ll;
typedef unsigned long long ull; template<class T> inline
void read(T& num) {
bool start=false,neg=false;
char c;
num=0;
while((c=getchar())!=EOF) {
if(c=='-') start=neg=true;
else if(c>='0' && c<='9') {
start=true;
num=num*10+c-'0';
} else if(start) break;
}
if(neg) num=-num;
}
/*==================split line==================*/
struct Edge{
int from,to,c,cap;
}e[maxm];
int dis[maxn],first[maxn],next[maxm],from[maxn];
bool inq[maxn];
int sume,n,m,k,S,T,f,ans;
void addedge(int x,int y,int c,int cap){
sume++; e[sume].from=x; e[sume].to=y; e[sume].c=c; e[sume].cap=cap;
next[sume]=first[x]; first[x]=sume;
sume++; e[sume].from=y; e[sume].to=x; e[sume].c=-c; e[sume].cap=0;
next[sume]=first[y]; first[y]=sume;
}
bool spfa(){
FORP(i,S,T) dis[i]=INF;
memset(inq,false,sizeof(inq));
queue<int> q;
dis[S]=0; inq[S]=true; q.push(S);
while (!q.empty()){
int now=q.front(); q.pop(); inq[now]=false;
for (int i=first[now];i;i=next[i])
if (dis[e[i].to]>dis[now]+e[i].c && e[i].cap){
dis[e[i].to]=dis[now]+e[i].c; from[e[i].to]=i;
if (!inq[e[i].to]){
inq[e[i].to]=true;
q.push(e[i].to);
}
}
}
return dis[T]==INF?false:true;
}
void mincost(){
int i=from[T],x=INF;
while (i){
x=min(x,e[i].cap);
i=from[e[i].from];
}
f+=x; i=from[T];
while (i){
//ans+=(x*e[i].c);
e[i].cap-=x; e[i^1].cap+=x;
i=from[e[i].from];
}
ans+=dis[T]*x;
}
void init(){
ans=0; memset(first,0,sizeof(first));
f=0; sume=1;
read(n); read(m); read(k);
S=0; T=n+n+2;
FORP(i,1,n) {
addedge(S,i,0,k); addedge(i+n,T,0,k);
}
//FORP(i,1,n) addedge(i,i+n,
FORP(i,1,m){
int u,v,w;
read(u);read(v);read(w);
u++; v++;
addedge(u,v+n,w,1);
}
}
void work(){
int ans=0;
while (spfa()) mincost();
}
void print(){
bool flag=true;
//FORP(i,2,sume) if (e[i].cap>0) {flag=false; break;}
if (f<n*k) flag=false;
if (!flag) printf("-1\n");
else printf("%d\n",ans);
}
int main(){
int cas; read(cas);
while (cas--){
init();
work();
print();
}
}