二分图的最小点权覆盖。

非常感谢巨巨的解答，还帮我画了一个图。

题目保证给出的边构成的图是一个二分图。

如果没有第三种类型的$frog$，那么问题就很简单了。即选择哪些点，覆盖住所有的边，并且要求选择的点的权值之和最小。可以转换成网络流来解决。

现在有第三种类型的$frog$，可以把这种$frog$拆成两个点，两点之间连边，然后其余和他有矛盾的点，分别向两个点中的一个点连边。画画图可以发现拆点之后的新图也是二分图。对这个图跑一次二分图的最小点权覆盖，如果拆点的边两端有一个点被选择，说明这个$frog$实际上是不选择的，如果拆点的边两端有两个点被选择，说明这个$frog$实际上被选择了，那么只要在结果上减去第三种类型的$frog$的权值和就可以了。

#include
     
      using namespace std;int n,m;int w[2010],p[2010],dis[2010];vector
      
       g[2010];const int maxn = 2100 + 10;const int INF = 0x7FFFFFFF;struct Edge{    int from, to, cap, flow;    Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){}};vector
       
        edges;vector
        
         G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];int s, t;void init(){    for (int i = 0; i < maxn; i++) G[i].clear();    edges.clear();}void AddEdge(int from, int to, int cap){    edges.push_back(Edge(from, to, cap, 0));    edges.push_back(Edge(to, from, 0, 0));    int w = edges.size();    G[from].push_back(w - 2);    G[to].push_back(w - 1);}bool BFS(){    memset(vis, 0, sizeof(vis));    queue
         
          Q;    Q.push(s);    d[s] = 0;    vis[s] = 1;    while (!Q.empty())    {        int x = Q.front();        Q.pop();        for (int i = 0; i
          
           e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t];}int DFS(int x, int a){ if (x == t || a == 0) return a; int flow = 0, f; for (int &i = cur[x]; i
           
            0) { edges[G[x][i]].flow+=f; edges[G[x][i] ^ 1].flow-=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[x] = -1; return flow;}int dinic(int s, int t){ int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow;}void B(int x){ queue
            
             Q; Q.push(x); dis[x]=0; while(!Q.empty()) { x = Q.front(); Q.pop(); for(int i=0;i