結果

問題 No.1324 Approximate the Matrix
コンテスト
ユーザー publfl
提出日時 2020-12-22 00:22:46
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,588 bytes
コンパイル時間 654 ms
コンパイル使用メモリ 60,924 KB
実行使用メモリ 366,416 KB
最終ジャッジ日時 2024-09-21 13:29:27
合計ジャッジ時間 4,139 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other TLE * 1 -- * 41
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <stdio.h>
#include <queue>
#include <vector>
#define MAX 123456789

int sq(int k)
{
	return k*k;
}

struct MCMF{ // vertex size : 402
	struct Edge{
		int first;
		int second;
		int capacity;
		int cost;
	};
	std::vector<int> V[1010][1010]; //V[i][j][k] = k'th edge of i->v
	std::vector<Edge> E;
	
	void setEdge(int first, int second, int capacity, int cost)
	{
		int n = E.size();
		E.push_back({first,second,capacity,cost});
		E.push_back({second,first,0,-cost});
		V[first][second].push_back(n);
		V[second][first].push_back(n+1);
	}
	
	int vSize = 402;
	int source,sink;
	
	int dist[1010],check[1010],prev[1010];
	std::vector<int> SPFA()
	{
		for(int i=0;i<=vSize;i++) check[i] = 0;
		for(int i=0;i<=vSize;i++) dist[i] = MAX;
		std::queue<int> Q;
		Q.push(source);
		dist[source] = 0;
		while(!Q.empty())
		{
			int v = Q.front();
			Q.pop();
			
			check[v] = 0;
			for(int i=0;i<=vSize;i++)
			{
				for(int k=0;k<V[v][i].size();k++)
				{
					int e = V[v][i][k];
					if(E[e].capacity>0)
					{
						if(dist[i]>dist[v]+E[e].cost)
						{
							dist[i] = dist[v] + E[e].cost;
							prev[i] = e;
							if(check[i]==0)
							{
								check[i] = 1;
								Q.push(i);
							}
						}
					}
				}
			}
		}
		
		std::vector<int> path;
		if(dist[sink]==MAX) return path;
		else
		{
			int v = sink;
			while(v!=source)
			{
				path.push_back(prev[v]);
				v = E[prev[v]].first;
			}
			return path;
		}
	}
	
	std::pair<int,int> getMCMF() // <Flow,Cost>
	{
		int flow = 0, cost = 0;
		while(1)
		{
			std::vector<int> path = SPFA();
			if(path.size()==0) return std::make_pair(flow,cost);
			else
			{
				int f = MAX, c = 0;
				for(int i=0;i<path.size();i++)
				{
					f = f<E[path[i]].capacity?f:E[path[i]].capacity;
					c += E[path[i]].cost;
				}
				flow += f;
				cost += f*c;
				for(int i=0;i<path.size();i++)
				{
					E[path[i]].capacity -= f;
					E[path[i]^1].capacity += f;
				}
			}
		}
	}	
}G;

int A[210],B[210];
int x[210][210];
int main()
{
	int a,b;
	scanf("%d%d",&a,&b);
	for(int i=1;i<=a;i++) scanf("%d",&A[i]);
	for(int i=1;i<=a;i++) scanf("%d",&B[i]);
	for(int i=1;i<=a;i++) for(int j=1;j<=a;j++) scanf("%d",&x[i][j]);
	
	G.source = 0;
	G.sink = 401;
	for(int i=1;i<=a;i++) G.setEdge(0,i,A[i],0);
	for(int j=1;j<=a;j++) G.setEdge(200+j,401,B[j],0);
	
	for(int i=1;i<=a;i++)
	{
		for(int j=1;j<=a;j++)
		{
			for(int k=0;k<=b;k++)
			{
				G.setEdge(i,200+j,1,-sq(x[i][j]-k)+sq(x[i][j]-k-1));
			}
		}
	}
	
	int sum = 0;
	for(int i=1;i<=a;i++) for(int j=1;j<=a;j++) sum += sq(x[i][j]);
	printf("%d",sum+G.getMCMF().second);
}
0