这道题其实不难。。。就是建图恶心了点。。。。emm。。。
题意：
多源多汇 + 拆边
青蛙跳柱子， 每根柱子都有一定的承载能力， 青蛙跳上去之后柱子的承载能力就会减一，跳到边界就能活 跳不到就over了，青蛙有一个最大的跳跃距离dis， 把每根柱子拆成两个点， 中间连一条边，为柱子的承载能力， 每个青蛙的初始位置都为一个源 边界为汇 ， 建立超级源s和超级汇t ， s连接所有青蛙的起点，权值为1， 边界和 距离青蛙起点小于dis的点连接t， 权值为INF， 并且建立u->u' u'->v 的边
看完题想建图的时候觉得暴力建图肯定会超时，然后实在想不出什么好的建图方法， 然后暴力建图， emm。。。竟然没超时。。。 还有注意output的英语语法！！！
Dinic + 弧优化：。。。。现在只会写这个了。。。
#include <iostream> #include <cstdio> #include <sstream> #include <cstring> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <cmath> #define MOD 2018 #define LL long long #define ULL unsigned long long #define maxn 1000000 #define Pair pair<int, int> #define mem(a, b) memset(a, b, sizeof(a)) #define _ ios_base::sync_with_stdio(0),cin.tie(0) //freopen("1.txt", "r", stdin); using namespace std; const int INF = 0x3f3f3f3f; int head[maxn], d[maxn], cur[maxn]; int n, m, s, t, dis; int cnt = 0; struct node{ int u, v, c, next; }Node[maxn*2]; void add_(int u, int v, int c) { Node[cnt].u = u; Node[cnt].v = v; Node[cnt].c = c; Node[cnt].next = head[u]; head[u] = cnt++; } void add(int u, int v, int c) { add_(u,v,c); add_(v,u,0); } bool bfs() { queue<int> Q; mem(d,0); d[s] = 1; Q.push(s); while(!Q.empty()) { int u = Q.front(); Q.pop(); for(int i=head[u]; i!=-1; i=Node[i].next) { node e = Node[i]; if(!d[e.v] && e.c > 0) { d[e.v] = d[e.u] + 1; Q.push(e.v); if(e.v == t) return 1; } } } return d[t] != 0; } int dfs(int u, int cap) { if(u == t || cap == 0) return cap; int ret = 0; for(int &i=cur[u]; i!=-1; i=Node[i].next) { node e = Node[i]; if(d[e.v] == d[u] + 1 && e.c > 0) { int V = dfs(e.v, min(cap, e.c)); Node[i].c -= V; Node[i^1].c += V; ret += V; cap -= V; if(cap == 0) break; } } return ret; } int Dinic() { int ans = 0; while(bfs()) { memcpy(cur, head, sizeof(head)); ans += dfs(s, INF); } return ans; } int main() { char str[50][50], map[maxn]; int bz[25][25]; int T, kase = 0; scanf("%d",&T); while(T--) { cnt = 0; int ret = 0; mem(bz,0); mem(head,-1); int ans = 0; scanf("%d%d",&n,&dis); for(int i=0; i<n; i++) scanf("%s",&str[i]); for(int i=0; i<n; i++) { int len = strlen(str[i]); if( i == 0) s = 0, t = 2 * len * n + 1; for(int j=0; j<len; j++) { ans++; int temp = str[i][j] - '0'; if(temp != 0) { add(ans, n*len + ans, temp); if(i-dis < 0 || i+dis >=n || j-dis <0 || j+dis >= len){ add(n*len+ans, t, INF); } for(int k=-dis; k<=dis; k++) { for(int g=-dis; g<=dis; g++) { int nx = i + k; int ny = j + g; if(nx == i && ny == j) continue; if(nx < 0 || nx >= n || ny < 0 || ny >= len || str[i][j] == '0' || abs(i-nx) + abs(j-ny) > dis) continue; add(n*len+ans, nx*len+ny+1, INF); // add(n*len+bz[nx][ny], ans, INF); } } } } } for(int i=0; i<n; i++) { scanf("%s",map); for(int j=0; j<strlen(map); j++) { if(map[j] == 'L') { ret++; add(s, i*strlen(map)+j+1, 1); } } } // for(int i=0; i<cnt; i++) // cout<< Node[i].u << " " << Node[i].v << " " <<Node[i].c<<endl; int op = ret - Dinic(); // for(int i=0; i<cnt; i++) // cout<< Node[i].u << " " << Node[i].v << " " <<Node[i].c<<endl; if(op > 1) printf("Case #%d: %d lizards were left behind. ",++kase,op); else if(op == 0) printf("Case #%d: no lizard was left behind. ",++kase); else if(op == 1) printf("Case #%d: 1 lizard was left behind. ",++kase); } return 0; }