#include #include #include #include #include using namespace std; static const int INF = INT_MAX / 1000; static const int NOT_LABELED = -1; template class MaxFlow { public: void reset(int numberOfNodes) { this->numberOfNodes = numberOfNodes; memset(graph, 0, sizeof(graph)); } void addEdge(int from, int to, int flow){ graph[from][to] += flow; } int get(int start, int goal){ int path[N]; int sizeOfNodes; int result = 0; while (searchPath(start, goal, path, sizeOfNodes)){ const int flow = getMaxFlow(path, sizeOfNodes); result += flow; updateGraph(path, sizeOfNodes, flow); } return result; } private: int numberOfNodes; int graph[N][N]; bool searchPath(int start, int goal, int path[], int& sizeOfNodes){ int label[N]; fill_n(label, numberOfNodes, NOT_LABELED); int open[N]; int sizeOfOpen = 0; open[sizeOfOpen++] = start; while (sizeOfOpen && label[goal] == NOT_LABELED){ const int from = open[--sizeOfOpen]; for (int to = 0; to < numberOfNodes; ++to){ if (label[to] != NOT_LABELED || graph[from][to] == 0){ continue; } label[to] = from; open[sizeOfOpen++] = to; } } if (label[goal] == NOT_LABELED){ return false; } sizeOfNodes = 0; int current = goal; while (current != start){ path[sizeOfNodes++] = current; current = label[current]; } path[sizeOfNodes++] = start; reverse(path, path + sizeOfNodes); return true; } int getMaxFlow(int path[], int sizeOfNodes){ int minFlow = INT_MAX; for (int i = 0; i < sizeOfNodes - 1; ++i){ minFlow = min(minFlow, graph[path[i]][path[i + 1]]); } return minFlow; } void updateGraph(int path[], int sizeOfNodes, int flow){ for (int i = 0; i < sizeOfNodes - 1; ++i){ const int from = path[i]; const int to = path[i + 1]; graph[from][to] -= flow; graph[to][from] += flow; } } }; MaxFlow<> maxFlow; int nodeSource() { return 0; } int nodeDest() { return nodeSource() + 1; } int nodeOrder(int orderIndex) { return nodeDest() + 1 + orderIndex; } int nodeTool(int N, int toolIndex) { return nodeOrder(N) + toolIndex; } int nodeSize(int N, int M) { return nodeTool(N, M); } int main() { for (int N, M, P; cin >> N >> M >> P && N && M;){ const int n = nodeSize(N, M); maxFlow.reset(n); int sumPay = 0; for (int i = 0; i < N; ++i){ int pay, numberOfTools; cin >> pay >> numberOfTools; maxFlow.addEdge(nodeSource(), nodeOrder(i), pay); sumPay += pay; for (int j = 0; j < numberOfTools; ++j){ int toolIndex; cin >> toolIndex; --toolIndex; maxFlow.addEdge(nodeOrder(i), nodeTool(N, toolIndex), INF); } } vector toolCosts(M); for (int i = 0; i < M; ++i){ cin >> toolCosts[i]; } for (int i = 0; i < P; ++i){ int toolIndex0, toolIndex1, pairCost; cin >> toolIndex0 >> toolIndex1 >> pairCost; --toolIndex0; --toolIndex1; const int pairEdgeCost = toolCosts[toolIndex0] + toolCosts[toolIndex1] - pairCost; toolCosts[toolIndex0] -= pairEdgeCost; maxFlow.addEdge(nodeTool(N, toolIndex0), nodeTool(N, toolIndex1), pairEdgeCost); } for (int i = 0; i < M; ++i){ maxFlow.addEdge(nodeTool(N, i), nodeDest(), toolCosts[i]); } cout << sumPay - maxFlow.get(nodeSource(), nodeDest()) << endl; } } /* ƒI[ƒ_[‚̐”N H‹ο‚ΜŽν—ήM Š„ˆψƒyƒA‚̐”P ƒI[ƒ_[1‚Μ•ρVX1 •K—v‚ȍH‹ο‚̐”K1 •K—v‚ȍH‹ο1 ... •K—v‚ȍH‹οK1 ...iNsŒJ‚θ•Τ‚΅j H‹ο1‚Μ‰ΏŠi ...iMsŒJ‚θ•Τ‚΅j Š„ˆψƒyƒA1‚̍H‹ο1 H‹ο2 ‰ΏŠi ...(PsŒJ‚θ•Τ‚΅j */