HNOI模拟 2016.3.31 百步穿杨

版权声明：都是TATQAQ2333大爷教我的 https://blog.csdn.net/u012076197/article/details/5121

#include
#include
#include
#include
#include
#include
using namespace std;
const char dr[]=“ AV<>“;
const int dx[5]={0-1100};
const int dy[5]={000-11};
const int inf=（1<<25）-1;

class LaserTowersDiv1
{
	public:
	int nm;
	char s[55][55];
	int I[55][55]J[55][55];
	int head[6666]adj[1000000]f[1000000]next[1000000]tot;
	int STdnlevel[6666]q[3333]qhqtmf;

	bool bfs（）
	{
		memset（level-1dn+1<<2）;
		qh=0q[qt=1]=S;
		level[S]=0;
		for（int uvi;qh		{
			u=q[++qh];
			for（i=head[u];i;i=next[i]）
				if（level[v=adj[i]]==-1&&f[i]>0）
				{
					level[v]=level[u]+1;
					if（v==T）return 1;
					q[++qt]=v;
				}
		}
		return 0;
	}

	int aug（int uint flow）
	{
		if（u==T）return flow;
		int left=flow;
		for（int ti=head[u];i&&left;i=next[i]）
			if（f[i]>0&&level[adj[i]]==level[u]+1）
			{
				t=aug（adj[i]min（leftf[i]））;
				left-=t;
				f[i]-=tf[i^1]+=t;
			}
		if（left==flow）level[u]=-1;
		return flow-left;
	}

	int dinic（）
	{
		while（bfs（））
			mf+=aug（Sinf）;
		return mf;
	}

	void addedge（int uint vint w）
	{tot++;adj[tot]=v;f[tot]=w;next[tot]=head[u];head[u]=tot;
	tot++;adj[tot]=u;f[tot]=0;next[tot]=head[v];head[v]=tot;}

	int laser（const char &c）
	{
		for（int i=1;i<=4;i++）
			if（c==dr[i]）return i;
		return 0;
	}

	int countMaxEnemies（vector board）
	{
		tot=1;
		n=board.size（）;m=board[0].size（）;
		memset（s‘#‘sizeof（s））;
		for（int i=1;i<=n;i++）
			for（int j=1;j<=m;j++）
			{
				s[i][j]=board[i-1][j-1];
				I[i][j]=++dn;
				J[i][j]=++dn;
				addedge（I[i][j]J[i][j]inf）;
			}
		S=++dnT=++dn;
		int ans=0;
		for（int i=1jrtwxyflag;i<=n;i++）
			for（j=1;j<=m;j++）
				if（r=laser（s[i][j]））
				{
					t=0;
					for（x=iy=j;s[x][y]!=‘#‘;x+=dx[r]y+=dy[r]）
						if（s[x][y]>=‘0‘&&s[x][y]<=‘9‘）t=max（ts[x][y]-‘0‘）;
					ans+=t;
					flag=（s[i][j]==‘A‘||s[i][j]==‘V‘）;
					if（flag）addedge（SI[i][j]inf）;
					else addedge（J[i][j]Tinf）;
					x=i+dx[r]y=j+dy[r];
					if（s[x][y]!=‘#‘）
					{
						if（flag）addedge（I[i][j]I[x][y]t）;
						else addedge（J[x][y]J[i][j]t）;
						for（;s[x+dx[r]][y+dy[r]]!=‘#‘;x+=dx[r]y+=dy[r]）
						{
							w=s[x][y]>=‘0‘&&s[x][y]<=‘9‘?t-s[x][y]+‘0‘:t;
							if（flag）addedge（I[x][y]I[x+dx[r]][y+dy[r]]w）;
							else addedge（J[x+dx[r]][y+dy[r]]J[x][y]w）;
						}
					}
				}
		ans-=dinic（）;
		return ans;
	}
};

LaserTowersDiv1 T;

int main（）
{
	freopen（“archery.in““r“stdin）;
	freopen（“archery.out““w“stdout）;
	int nm;
	string s;
	vector a;
	cin>>n>>m;
	for（int i=0;i>sa.push_back（s）;
	cout<	return 0;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件     150171  2016-03-30 22:55  2016模拟题2 - Solution.pdf

     文件     165460  2016-03-30 22:55  2016模拟题2.pdf

     文件       2742  2016-03-20 20:28  data\archery\archery.cpp

     文件     965264  2016-03-20 20:28  data\archery\archery.exe

     文件      13404  2016-03-20 20:28  data\archery\archery.o

     文件         26  2016-03-20 20:11  data\archery\archery0.in

     文件          4  2016-03-20 20:11  data\archery\archery0.out

     文件         33  2016-03-20 20:31  data\archery\archery1.in

     文件          4  2016-03-20 20:13  data\archery\archery1.out

     文件         40  2016-03-20 20:14  data\archery\archery2.in

     文件          4  2016-03-20 20:14  data\archery\archery2.out

     文件       2558  2016-03-20 20:17  data\archery\archery3.in

     文件          5  2016-03-20 20:18  data\archery\archery3.out

     文件       2358  2016-03-20 20:20  data\archery\archery4.in

     文件          5  2016-03-20 20:20  data\archery\archery4.out

     文件       2409  2016-03-20 20:32  data\archery\archery5.in

     文件          5  2016-03-20 20:21  data\archery\archery5.out

     文件       2456  2016-03-20 20:22  data\archery\archery6.in

     文件          5  2016-03-20 20:22  data\archery\archery6.out

     文件       2408  2016-03-20 20:23  data\archery\archery7.in

     文件          5  2016-03-20 20:23  data\archery\archery7.out

     文件       2360  2016-03-20 20:24  data\archery\archery8.in

     文件          5  2016-03-20 20:25  data\archery\archery8.out

     文件       2405  2016-03-20 20:26  data\archery\archery9.in

     文件          5  2016-03-20 20:26  data\archery\archery9.out

     文件     109412  2016-03-20 19:17  data\archery\tc.txt

     文件        917  2016-03-20 16:23  data\language\gen.cpp

     文件     963268  2016-03-20 16:24  data\language\gen.exe

     文件       3138  2016-03-20 16:24  data\language\gen.o

     文件         92  2016-03-20 16:22  data\language\gen.txt

............此处省略61个文件信息