说是最大权闭合图....
比赛时没敢写....
题意
一共同拥有n个任务，m个技术
完毕一个任务可盈利一些钱，学习一个技术要花费钱
完毕某个任务前须要先学习某几个技术
可是可能在学习一个任务前须要学习另几个任务
求最多能赚多少钱咯
先将缩点将须要一起学掉的技术缩成一个点
建s--任务 权值为该任务盈利多少钱
建技术（缩点后）-t 权值为学习这技术的花费（总）
任务-技术 （完毕该任务所需的每一个技术都须要建边）权值为INF
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#include<ctype.h>
#include<math.h>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
#include<queue>
#include<stack>
#include<vector>
#include<deque>
#include<set>
#include<map>
//N为最大点数
#define M 150
//M为最大边数
const int MAXN = 2999;//点数的最大值
const int MAXM = 2222;//边数的最大值
const int INF = 0x3f3f3f3f;
struct Edge{
int from, to, nex;
bool sign;//是否为桥
}edge[M<<1];
int head[MAXN], edgenum;
void add(int u, int v){//边的起点和终点
Edge E={u, v, head[u], false};
edge[edgenum] = E;
head[u] = edgenum++;
}
int DFN[333], Low[333], Stack[333], top, Time; //Low[u]是点集{u点及以u点为根的子树} 中(全部反向弧)能指向的(离根近期的祖先v) 的DFN[v]值(即v点时间戳)
int taj;//连通分支标号，从1開始
int Belong[333];//Belong[i] 表示i点属于的连通分支
bool Instack[333];
vector<int> bcc[333]; //标号从1開始
void tarjan(int u ,int fa)
{
DFN[u] = Low[u] = ++ Time ;
Stack[top ++ ] = u ;
Instack[u] = 1 ;
for (int i = head[u] ; ~i ; i = edge[i].nex )
{
int v = edge[i].to;
if(DFN[v] == -1)
{
tarjan(v , u);
Low[u] = min(Low[u] ,Low[v]) ;
if(DFN[u] < Low[v])
{
edge[i].sign = 1;//为割桥
}
}
else if(Instack[v])
{
Low[u] = min(Low[u] ,DFN[v]) ;
}
}
if(Low[u] == DFN[u])
{
int now;
taj ++ ;
bcc[taj].clear();
do{
now = Stack[-- top] ;
Instack[now] = 0 ;
Belong [now] = taj ;
bcc[taj].push_back(now);
}while(now != u) ;
}
}
void tarjan_init(int all){
memset(DFN, -1, sizeof(DFN));
memset(Instack, 0, sizeof(Instack));
top = Time = taj = 0;
for(int i=1;i<=all;i++)
if(DFN[i]==-1 )
tarjan(i, i); //注意開始点标！！！
}
vector<int>G[333];
int du[333];
void suodian(){
memset(du, 0, sizeof(du));
for(int i = 1; i <= taj; i++)
G[i].clear();
for(int i = 0; i < edgenum; i++)
{
int u = Belong[edge[i].from], v = Belong[edge[i].to];
if(u!=v)
{
G[u].push_back(v), du[v]++;
}
}
}
struct Edge1
{
int to,next,cap,flow;
}edge1[MAXM];//注意是MAXM
int tol;
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
//加边，单向图三个參数，双向图四个參数
void addedge (int u,int v,int w,int rw=0)
{
edge1[tol].to = v;edge1[tol].cap = w;edge1[tol].next = head[u];
edge1[tol].flow = 0;head[u] = tol++;
edge1[tol].to = u;edge1[tol].cap = rw;edge1[tol]. next = head[v];
edge1[tol].flow = 0;head[v]=tol++;
}
//输入參数：起点、终点、点的总数
//点的编号没有影响，仅仅要输入点的总数
int sap(int start,int end, int N)
{
memset(gap,0,sizeof(gap));
memset(dep,0,sizeof(dep));
memcpy(cur,head,sizeof(head));
int u = start;
pre[u] = -1;
gap[0] = N;
int ans = 0;
int i;
while(dep[start] < N)
{
if(u == end)
{
int Min = INF;
for( i = pre[u];i != -1; i = pre[edge1[i^1]. to])
{
if(Min > edge1[i].cap - edge1[i]. flow)
Min = edge1[i].cap - edge1[i].flow;
}
for( i = pre[u];i != -1; i = pre[edge1[i^1]. to])
{
edge1[i].flow += Min;
edge1[i^1].flow -= Min;
}
u = start;
ans += Min;
continue;
}
bool flag = false;
int v;
for( i = cur[u]; i != -1;i = edge1[i].next)
{
v = edge1[i]. to;
if(edge1[i].cap - edge1[i].flow && dep[v]+1 == dep[u])
{
flag = true;
cur[u] = pre[v] = i;
break;
}
}
if(flag)
{
u = v;
continue;
}
int Min = N;
for( i = head[u]; i != -1;i = edge1[i]. next)
{
if(edge1[i].cap - edge1[i].flow && dep[edge1[i].to] < Min)
{
Min = dep[edge1[i].to];
cur[u] = i;
}
}
gap[dep[u]]--;
if(!gap[dep[u]]) return ans;
dep[u] = Min+1;
gap[dep[u]]++;
if(u != start) u = edge1[pre[u]^1].to;
}
return ans;
}
int a[MAXN],b[MAXN],cost[MAXN];
vector<int>q[222];
void init(){memset(head, -1, sizeof(head)); edgenum=0;tol=0;}
int main()
{
int t,cas=1;
int n, m;//n m 为点数和边数
// freopen("in.txt","r",stdin);
scanf("%d",&t);
while(t--)
{
init();
int sum=0;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
sum+=a[i];
}
for(int i=1;i<=m;i++)
{
cost[i]=0;
scanf("%d",&b[i]);
}
for(int i=1;i<=n;i++)
{
int k,c;
q[i].clear();
scanf("%d",&k);
for(int j=0;j<k;j++)
{
scanf("%d",&c);
q[i].push_back(c);
}
}
for(int i=1;i<=m;i++)
for(int j=1;j<=m;j++)
{
int a;
scanf("%d",&a);
if(a)
add(i,j);
}
tarjan_init(m);
suodian();
for(int i=1;i<=m;i++)
{
int v=Belong[i];
cost[v]+=b[i];
}
init();
int s=0,end=taj+n+1;
for(int i=1;i<=n;i++)
{
addedge(s,taj+i,a[i],0);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<q[i].size();j++)
{
addedge(taj+i,Belong[q[i][j]+1],INF,0);
}
}
for(int i=1;i<=taj;i++)
{
addedge(i,end,cost[i],0);
for(int j=0;j<G[i].size();j++)
{
addedge(i,G[i][j],INF,0);
}
}
printf("Case #%d: ",cas++);
printf("%d
",sum-sap(s,end,taj+n+2));
}
return 0;
}