读懂题之后很容易就能想到跟二分图最大匹配的模型很像，用hero和monster去匹配，可以直接·套版子，难点在于药瓶可以增加匹配路线，开始我想的很复杂，从边数的大到小排了序再去增加匹配，结果还是wa，后来想到在匈牙利算法中的matched数组已经存了匹配的点，那么我只要再跑一边匈牙利算法让剩下没有匹配的点也进行匹配，然后的到的结果ans2与k比较取较小者即可
#include<bits/stdc++.h> using namespace std; const int maxn = 505; int n,m,k,ans; int vis[maxn][maxn]; int ask[maxn],matched[maxn]; inline bool found(int x){ //dfs找增广路 for (int i = 1 ; i <= m ; i++) if (vis[x][i]){ if (ask[i]) continue; ask[i] = 1; if (!matched[i] || found(matched[i])) { matched[i] = x ; return true; } } return false; } inline int match(){ int cnt = 0;//cnt是计数器 for (int i = 1 ; i <= n ; i++){ memset(ask,0,sizeof(ask)); if (found(i)) cnt++; //找到了就加1 } ans = cnt; return ans; } int main(){ scanf("%d%d%d",&n,&m,&k);//结点个数分别为n,m，边数为e for(int i = 1; i <= n; i++){ int cnt; cin>>cnt; for(int j = 1; j <= cnt; j++){ int v; cin>>v; vis[i][v] = 1; } } int ans1 = match();//匈牙利算法，见上 int ans2 = match();//再跑一边匈牙利算法 printf("%d\n",ans1+min(ans2,k));//如果第二次跑的结果小于k则取ans2，否则取k return 0; }