题目和数据在这里: 链接：http://pan.baidu.com/s/1nu5JRzr 密码：wt2n
题目大意：给你一个棋盘，格子有三种类型：指定方向的箭塔，目标，或者空地，每个箭塔可以选中一个目标（当然每个目标只能被选一次），求最大收益
额外条件：箭塔的射程内不会有其他箭塔
限制：箭塔的攻击轨迹不能相交
发现隐藏条件：箭塔的攻击轨迹不能相交，那么每个格子只能被一个箭塔穿过。因为箭塔的射程内不会有其他箭塔，
那么若一个格子在一个向右的箭塔的攻击范围内，就不可能在一个向左的箭塔的范围里。
所以我们实际上只用给每个格子定方向：横向或纵向。
这样方向就只有两种，问题显然可以转化成网络流-最小割。
考虑限制条件：
1.每个格子只有一种方向：这个显然可以拆点解决
2.每个箭塔只能选一个目标：设射程内点权最大值为Max，将Max加入总贡献。我们将射程内的点按顺序连起来，每个点和下个点的边权为Max-这个点点权，这条边被割代表选择了该点。若这条链跟汇点（或者源点）不相连，则表示射程里的每个点都不在其他箭塔的攻击范围内。
3.每个箭塔代表的方向已经确定
总贡献-最小割即为答案
代码如下：
/*
* @Author: 逸闲
* @Date: 2016-04-21 19:35:12
* @Last Modified by: 逸闲
* @Last Modified time: 2016-04-21 20:41:46
*/
#include "cstdio"
#include "cstdlib"
#include "iostream"
#include "algorithm"
#include "cstring"
#include "queue"
using namespace std;
#define INF 0x3F3F3F3F
#define MAX_SIZE 55
#define Eps
#define Mod
#define Get(x, a) (x ? x -> a : 0)
inline int Get_Int()
{
int Num = 0, Flag = 1;
char ch;
do
{
ch = getchar();
if(ch == '-')
Flag = -Flag;
}
while(ch < '0' || ch > '9');
do
{
Num = Num * 10 + ch - '0';
ch = getchar();
}
while(ch >= '0' && ch <= '9');
return Num * Flag;
}
namespace Flow_Network
{
class Edge
{
public:
int To, Next, C;
}Edges[MAX_SIZE * MAX_SIZE * MAX_SIZE * 2];
int S, T, Total = 1;
int Distance[MAX_SIZE * MAX_SIZE * 2], Front[MAX_SIZE * MAX_SIZE * 2];
inline void Add_Edge(int From, int To, int C)
{
Edges[++Total].To = To;
Edges[Total].Next = Front[From];
Edges[Total].C = C;
Front[From] = Total;
}
inline void Add_Edges(int From, int To, int C)
{
Add_Edge(From, To, C);
Add_Edge(To, From, 0);
}
inline bool BFS()
{
queue<int> Queue;
memset(Distance, 0, sizeof(Distance));
Distance[S] = 1;
Queue.push(S);
while(!Queue.empty())
{
int Now = Queue.front();
Queue.pop();
for(int i = Front[Now]; i; i = Edges[i].Next)
if(Edges[i].C && !Distance[Edges[i].To])
{
Distance[Edges[i].To] = Distance[Now] + 1;
Queue.push(Edges[i].To);
}
}
return Distance[T];
}
int DFS(int Now, int In)
{
if(Now == T)
return In;
int Rest = In;
for(int i = Front[Now]; i; i = Edges[i].Next)
if(Edges[i].C && Distance[Edges[i].To] == Distance[Now] + 1)
{
int Increment = DFS(Edges[i].To, min(Edges[i].C, Rest));
Rest -= Increment;
Edges[i].C -= Increment;
Edges[i ^ 1].C += Increment;
if(!Rest)
return In;
}
if(Rest == In)
Distance[Now] = 0;
return In - Rest;
}
inline int Max_Flow()
{
int Flow = 0;
while(BFS())
Flow += DFS(S, INF);
return Flow;
}
}
int N, M, Total, Ans;
int Movex[] = {0, -1, 1, 0, 0}, Movey[] = {0, 0, 0, -1, 1};
char Map[MAX_SIZE][MAX_SIZE];
inline int Point(int x, int y)
{
return (x - 1) * M + y;
}
inline int Find(char ch)
{
if(ch == 'A')
return 1;
else if(ch == 'V')
return 2;
else if(ch == '<')
return 3;
else if(ch == '>')
return 4;
return 0;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("archery.in", "r", stdin);
freopen("archery.out", "w", stdout);
#endif
cin >> N >> M;
for(int i = 1; i <= N; ++i)
scanf("%s", Map[i] + 1);
Total = N * M;
Flow_Network::S = 0;
Flow_Network::T = Total * 2 + 1;
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
{
if(Map[i][j] >= '0' && Map[i][j] <= '9')
Map[i][j] -= '0';
Flow_Network::Add_Edges(Point(i, j), Point(i, j) + Total, INF);
}
for(int i = 1; i <= N; ++i)
for(int j = 1; j <= M; ++j)
if(int Direction = Find(Map[i][j]))
{
int Max = 0, Flag = Direction <= 2;
if(Flag)
Flow_Network::Add_Edges(Flow_Network::S, Point(i, j), INF);
else
Flow_Network::Add_Edges(Point(i, j) + Total, Flow_Network::T, INF);
for(int x = i + Movex[Direction], y = j + Movey[Direction]; Map[x][y]; x += Movex[Direction], y += Movey[Direction])
if(Map[x][y] <= 9)
Max = max(Max, (int)Map[x][y]);
for(int x = i + Movex[Direction], y = j + Movey[Direction], a = i, b = j; Map[x][y]; a = x, b = y, x += Movex[Direction], y += Movey[Direction])
{
int C = Max;
if(Map[a][b] <= 9)
C -= Map[a][b];
if(Flag)
Flow_Network::Add_Edges(Point(a, b), Point(x, y), C);
else
Flow_Network::Add_Edges(Point(x, y) + Total, Point(a, b) + Total, C);
}
Ans += Max;
}
cout << Ans - Flow_Network::Max_Flow() << endl;
fclose(stdin);
fclose(stdout);
return 0;
}